Поясняющий пример к изученному материалу

Для графа G=(Y,V) (рис.1) построить матрицы смежностей и инциденций, и по матрице смежностей – матрицу достижимостей, выделить связные (сильные) компоненты. Найти число путей длиной 3 из У₆ в У₂

Решение

Матрица смежностей:

Матрица инциденций:

Матрица контрдостижимостей:

Связные (сильные) компоненты:

{y4, y5, y6}=f

Найдем число путей длиной 3 из У₆ в У₂.

Пример. Представить граф.

Турнир по волейболу проводится по круговой системе между n командами. Докажите, что если какие-нибудь две команды одержали в турнире одинаковое число побед, то найдутся среди участников три команды I, II и III такие, что I выиграла у II, II выиграла у III, a III выиграла у I.

Подсказка. Пусть А и В - две команды, одержавшие одинаковое число к побед. Пусть к тому же А выиграла у В.