Связная графа

Cтраница 3

Любой граф состоит из связных кусков. Поэтому достаточно изучить связные графы. [31]

Если все вершины G принадлежат дереву Т, то говорят, что дерево покрывает) граф G. Очевидно, что только связные графы имеют покрывающие деревья и только деревья имеют единственные покрывающие деревья. [32]

Полный граф К5 ( а и полный двудольный граф Кз з ( б. [33]

Очевидно, что граф планарен тогда и только тогда, когда планарны все его связные компоненты. Поэтому для определения планарности рассматривают связные графы. Распространенная методика определения планарностизаключается в нахождении в графе G максимального цикла С ( лучше всего гамильтонова) и размещении его на плоскости в виде замкнутой самопересекающейся кривой. Далее в оставшейся части определяют пересекающиеся по ребрам пути и предпринимают попытки разместить каждый из этих путей либо полностью внутри С, либо полностью вне С. Если таким образом размещается весь граф, то он планарен, в обратном случае не планарен. [34]

При этом достаточно будет рассматривать связные графы - для несвязных графов задача сводится к независимой раскраске отдельных компонент связности. [35]

Часто класс графов можно описать на языке блоков, содержащихся в графах из этого класса. Например, деревья являются такими связными графами, все блоки которых изоморфны графу Kz; у графов блоков все блоки представляют собой полные графы1; кактусы являются связными графами, у которых блоки - либо ребра, либо циклы; множество всех связных графов, не имеющих висячих вершин, совпадает в точности с множеством всех нетривиальных связных графов, у которых концевые блоки не изоморфны графу Кг. [36]

Итак, классификация корневых систем сводится к классификации диаграмм Дынкина. Таким образом, достаточно классифицировать все связные графы Дынкина. [37]

Компоненты связности любого графа G являются максимальными ( по включению) связными подграфами графа G. Для решения многих задач достаточно рассматривать только связные графы. [38]

Нас интересуют только связные многообразия, а значит, и связные графы. [39]

Все мы знакомы с понятием генеалогического дерева; обобщение этого понятия изучается в настоящей главе. Здесь также затронуты вопросы, относящиеся к остовным деревьям в связных графах и замечательному результату Кэли ( в § 10) о перечислении помеченных деревьев. В последнем параграфе рассмотрены некоторые приложения теории графов. [40]

Связные графы с четырьмя ребрами. [42]

Покажем, что звезда / d 3 не является реберным графом. Тогда граф Я имеет 4 ребра, поскольку в Ki3 четыре вершины, и, кроме того, граф Я должен быть связным. Все связные графы с четырьмя ребрами приведены на рис. 8.2. Так как. Я может быть только одним из трех деревьев. Таким образом, / d 3 не есть реберный граф. В дальнейшем мы увидим, что граф / Сьз играет важную роль при установлении основных свойств реберных графов. Первый результат о реберных графах - утверждение ( 2) приведенной ниже теоремы - полученный Крауцем [1], довольно близок к самому определению реберного графа. [43]

Ориентированный граф называется тотальным, если каждая пара различных вершин соединяется, по крайней мере, в одном направлении путем. Заметим, что антисимметрический полный граф является частным случаем тотального графа, в котором вышеупомянутые пути представляются одиночными дугами. Все сильно связные графы также являются тотальными. Следующий результат, полученный Камьоном и приводимый без доказательства, применим ко всем тотальным графам. [44]

Понятия радиус, центр и диаметр могут быть обобщены на ориентированные графы определенных типов. Если мы переопределим d ( v, w) как число дуг в кратчайшем пути из v к w, то нужно либо предположить, что существует путь из v к w для каждой v и w, либо считать, что понятие радиусов и диаметров не определены для некоторых ориентированных графов. Последнее условие можно устранить, считая, что рассматриваются только сильно связные графы. [45]

Страницы: 1 2 3 4