Примеры решения задач

Пример 1. Построить матрицу инцидентности гиперграфа Н = (Х, Е), изображенного на рис. 17.31.

Рис. 17.31. Гиперграф H

Граф, изображенный на рис. 17.31. можно задать следующей матрицей инцидентности.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Дайте определение гиперграфа.

2. Какие две вершины, либо два ребра гиперграфа считают смежными?

3. Как составляется матрица инцидентности гиперграфа?

4. Дайте определение цепи в гиперграфе.

5. Как составляется матрица смежности гиперграфа?

6. Каким образом для гиперграфа можно построить двойственный граф?

7. Какой гиперграф считается деревом?

8. Что такое раскраска гиперграфа?

9. Дайте определение двудольного графа Кенига.

10. Как строится двудольный граф Кенига?