Пример 15. Существует ли компания из шести человек, в которой каждый знаком с двумя, и только с двумя другими?

Существует ли компания из шести человек, в которой каждый знаком с двумя, и только с двумя другими? Постройте граф.

Решение.

Вариантов таких компаний может быть два.

Рис.5

В первом случае а) мы имеем связный граф, во втором б) – несвязный.

Ребро ( ) называется мостом, если в графе G(X,T), полученном после удаления ребра ( ), вершины и несвязны.

Рис.6

В исходном графе ребро ( ) является мостом.

Существует несколько признаков мостов:

1) Ребро ( ) является мостом тогда, и только тогда, когда ( ) является единственным путем, соединяющим вершины .

2) Ребро ) является мостом тогда, и только тогда, когда найдутся две вершины , такие, что любой путь, соединяющий их, содержит вершины .

3) Ребро ) является мостом тогда, и только тогда, когда оно не принадлежит ни одному циклу.

Связный граф без циклов называется деревом.