Составители:
Рубрика:
110
Приведем без доказательства эту теорему. Пусть имеется направлен
ный полностью связанный граф G, т. е. все вершины связаны со всеми
остальными вершинами графа стрелками. Назовем вершину, в кото
рую только входят стрелки и ни одна не выходит из этой вершины,
побитой вершиной. Назовем некоторое множество вершин, в которое
только входят стрелки и ни одна не выходит из этого множества (при
чем между вершинами множества стрелки могут иметь произвольное
направление), побитым множеством.
Теорема о направленных графах. Если граф G не содержит поби+
тых вершин и побитых множеств вершин, то всегда в этом графе
существует направленный путь, выходящий из любой вершины гра+
фа и проходящий через все остальные вершины.
Таким образом, если ваша любимая команда не проиграла всех игр, у вас
имеются шансы утверждать, что она – самая лучшая команда турнира!
5.20. Задачи для контрольной
1. Задан граф списком ребер:
N арбер
123456789 011121
ынишреВ
AABBCCDEEGBG
ынишреВ
BBCCDFEFGFFA
Начертите его графическое изображение на плоскости, постройте
его матрицы инциденции и смежности. Определите тремя способами
число его ребер.
2. Теорема о направленных графах. Сформулируйте теорему и при
ведите пример с графом, имеющим не менее семи вершин.
3. Задан граф списком ребер:
N арбер
123456789 011121
ынишреВ
EADBCCDEEGBG
ынишреВ
EBDCDFEFGFFA
Начертите его графическое изображение на плоскости, постройте
его матрицы инциденции и смежности. Определите тремя способами
число его ребер.
4. Поясните, что такое цикломатическое число графа. Приведите
примеры.
5. Задан граф списком ребер:
N арбер
123456789 011121
ынишреВ
EADBCEDEEDBG
ынишреВ
EBDCDDEFGDFA
Страницы
- « первая
- ‹ предыдущая
- …
- 108
- 109
- 110
- 111
- 112
- …
- следующая ›
- последняя »
