Упражнения

2.1. Покажите, что на шести вершинах существует точно шесть неизоморфных деревьев, а на семи вершинах — 11. Нарисуйте все деревья.

2.2. Покажите, что дерево является двудольным графом.

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

а) содержит вершин;

б) содержит ребер;

в) — связный подграф;

г) не содержит циклов.

2.4. Докажите, что любое висячее ребро (ребро, инцидентное висячей вершине) связного графа G содержится в каждом его остове.

2.5. Докажите, что каждое ребро связного графа G является ветвью какого-либо остова этого графа.

2.6. Докажите, что в дереве каждая вершина, степень которой больше единицы, является точкой сочленения.

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

2.8. Докажите или опровергните: любые два ребра неразделимого графа содержатся в некотором базисном цикле.

2.9. При каких условиях любые два ребра графа G могут быть хордами некоторого кодерева графа

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

2.11. Покажите, что цикломатическое число любого графа не может быть отрицательным. Приведите пример графа, цикломатическое число которого равно 0.

2.12. Рассмотрите следующие две операции надграфами:

а) Если вершине инцидентны только два ребра то заменить единственным ребром, соединяющим v и

б) Заменить любое ребро (их, ) двумя ребрами где — новая вершина, не входящая в граф G. Докажите, что цикломатическое число графа является инвариантным относительно этих операций.

2.13. Связный граф G является минимально-связным, если для каждого ребра графа G граф — несвязный. Докажите, что связный граф является деревом тогда и только тогда, когда он минимально-связный.

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

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

2.16. Докажите, что каждый связный граф содержит разрезающее множество.

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

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

2.19. Докажите, что разрез в связном графе G является разрезающим множеством или объединением нескольких реберно-непересекающихся разрезающих множеств графа

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

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

2.22. Пусть С — цикл в графе G, а — любые ребра цикла С. Докажите, что существует такое разрезающее множество S, что

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

2.24. а) Пусть — два цикла графа G. Пусть — ребро, принадлежащее циклам а - ребро, принадлежащее только циклу Докажите, что существует такой цикл что принадлежит циклу Приведите доказательство того случая, когда в . а) термин «цикл» заменен термином «разрезающее множество».

Примечание. Это утверждение является одним из постулатов, использованных в работе [2.6] при определении «циклов» матроида (гл. 10).

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

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

2.27. Центральная вершина графа — это такая вершина что значение является наименьшим из возможных, где — расстояние между . Покажите, что дерево имеет либо только одну центральную вершину, либо две смежные центральные вершины.

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

Примечание: см, упр. 2.23.