Упражнения

1.1. Пусть G — такой граф на вершинах и ребрах, что вершины имеют степень k или Докажите, что если G имеет вершин степени k и вершин степени то

1.2. Доказать или опровергнуть:

а) объединение любых двух различных замкнутых маршрутов, соединяющих две вершины, содержит цикл; б) объединение любых двух различных путей, соединяющих вершины, содержит цикл.

1.3. Докажите, что если в графе G существуют пути между вершинами а и b, а также между b и с, то существует путь между а и с.

1.4. Пусть — два различных пути между двумя вершинами графа. Докажите, что является циклом или объединением нескольких реберно-непересекающихся циклов в графе.

1.5. Докажите, что замкнутая цепь, все вершины которой имеют степень два, является циклом.

1.6. Покажите, что если два различных цикла графа G содержат ребро , то в G существует цикл, не содержащий е.

1.7. Покажите, что в простом графе существует путь по крайней мере длины k. Покажите также, что G имеет цикл длины по крайней мере если

1.8. Докажите, что граф G является связным тогда и только тогда, когда для каждого разбиения множества V с непустыми существует ребро в G, соединяющее вершину из с вершиной из .

1.9. Докажите, что простой граф вершинами и k компонентами может иметь, самое большее, ребер. Используя этот результат, докажите, что граф G должен быть связным, если он имеет больше ребер.

1.10. Докажите, что если связный или несвязный граф G имеет точно две вершины нечетной степени, то должен существовать путь, соединяющий эти две вершины.

1.11. Докажите, что если простой граф G не является связным, то связно его дополнение

1.12. Пусть G — такой граф на вершинах и ребрах, что Докажите, что G — несвязный граф.

1.13. Докажите, что если для графа G на вершинах и ребрах выполняется неравенство то G содержит циклическое ребро.

1.14. Докажите, что простой граф G на вершинах является связным, если

1.15. Покажите, что простой граф G, имеющий по крайней мере две вершины, содержит две вершины одинаковой степени.

1.16. Покажите, что если граф является простым и связным, но неполным, то он имеет такие три вершины , что ребра (и, ) содержатся в Е, а ребро — не содержится.

1.17. Если вершины кип связаны в графе G, то расстояние между и и и, обозначаемое через является длиной наикратчайшего -пути в G. Если в графе G не существует -пути, то определяем расстояние как бесконечное. Максимальное расстояние между двумя вершинами в G называется диаметром G. Покажите, что если G имеет диаметр то G имеет диаметр

1.18. Обхватом графа G является длина наикратчайшего цикла в G. Если G не имеет циклов, то определяем обхват графа G как бесконечный. Покажите, что -однородный граф обхвата 4 имеет по крайней мере вершин.

1.19. Простой граф G называется самодополнительным, если он изоморфен своему дополнению G. Докажите, что число вершин самодополнигельного графа должно равняться или где k — целое число.

1.20. Докажите, что простой граф на вершинах не является двудольным, если он имеет более ребер.

1.21. Докажите, что граф является двудольным тогда и только тогда, когда все его циклы четной длины.

1.22. Постройте простой кубический граф на вершинах, не имеющий треугольников.

Примечание: граф называется кубическим, если он -однородный; треугольник — это цикл длины 3.

1.23. Докажите, что если v — точка сочленения в простом графе G, то она не является точкой сочленения в

1.24. Докажите, что приведенные ниже свойства графа G на 3 вершинах эквивалентны:

а) граф G является неразделимым;

б) любые две вершины в G входят в общий цикл;

в) для любой вершины v и любого ребра графа G существует цикл, содержащий и v, и

г) любые два ребра в G входят в общий цикл;

д) пусть даны две вершины и одно ребро в графе G; тогда существует путь, который соединяет эти две вершины и содержит данное ребро;

е) для любых трех различных вершин в G найдется путь, соединяющий любые две из них и включающий третью;

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

1.25. Покажите, что если граф G не содержит циклов четной длины, то каждый блок в G является либо либо либо циклом нечетной длины.

1.26. Покажите, что связный граф, не являющийся блоком, имеет два блока с общей вершиной. Пусть — число блоков графа , включающих вершину . Покажите, что число блоков графа G равно где — число компонент графа

1.27. Пусть с (В) — число точек сочленения связного графа G, являющихся вершинами блока В. Тогда число точек сочленения графа G определяется по формуле

1.28. Мостом графа G является такое ребро , что имеет больше компонент, чем G. Докажите:

Рис. 1.20.

Рис. 1.21

а) ребро связного графа G является мостом тогда и только тогда, когда существуют такие вершины и что лежит на каждом -пути в

б) ребро графа G является мостом в G тогда и только тогда, когда в графе G нет ни одного цикла, содержащего это ребро.

1.29. Являются ли графы, изображенные на рис. 1.20, изоморфными? Почему?

1.30. Покажите, что два графа на рис. 1.21 не изоморфны.

1.31. Определите все неизоморфные простые графы порядков 3 и 4. Примечание: существует только 4 неизоморфных графа с тремя вершинами и 11 — с четырьмя вершинами.

1.32. Докажите, что любые два простых связных графа на вершинах, каждая степени 2, являются изоморфными.