Неориентированный граф задан матрицей инцидентности Чему равно хроматическое число графа?

6 ноября 2025
Высшая математика

Условие:

Неориентированный граф задан матрицей инцидентности

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₃ → ребро м...