Условие:
Неориентированный граф задан матрицей инцидентности
| 1 | 0 | 1 | 0 | 1 |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
Чему равно хроматическое число графа?
Чему равно хроматическое число графа?
Решение:
Рассмотрим матрицу инцидентности графа:
Строки – вершины (v₁, v₂, v₃, v₄); Столбцы – ребра.
Матрица: v₁: 1 0 1 0 1 v₂: 0 1 1 1 1 v₃: 1 1 0 1 0 v₄: 0 0 0 0 0
Шаг 1. Определим ребра по столбцам (в простом неориентированном графе в каждом столбце должны стоять ровно две единицы):
• Столбец 1: единицы в строках v₁ и v₃ → ребро между v₁ и v₃. • Столбец 2: единицы в строках v₂ и v₃ → ребро м...