Несвязный граф

Cтраница 4

Исходный граф ( а, два возможных дерева [ одно - лагранжево дерево ( б. другое - в ] и фундаментальные циклы ( г. [46]

Несвязный граф имеет несколько деревьев - по числу связных компонентов. Совокупность деревьев несвязного графа называют лесом F графа. [47]

Несвязный граф имеет несколько деревьев - по числу связных компонент. Совокупность деревьев несвязного графа называют лесо м F графа. [48]

Если G - вполне несвязный граф, то утверждение очевидно. Если в графе G число ребер минимально ( скажем т0), то удаление любого ребра должно привести к увеличению числа компонент на единицу. Таким образом, в получившемся графе будет п вершин, k 1 компонент и от0 - 1 ребер. Следовательно, в силу индуктивного предположения от0 - 1 п - ( k 1), откуда сразу же получается т0 п - k, что и утверждалось. [49]

Подграф, являющийся полным ( пустым) графом, такой, что любой включающий его подграф исходного графа не является полным ( пустым), называется максимальным полным ( пустым) подграфом. Наибольший связный подграф несвязного графа называется компонентом связности. Подграф, являющийся деревом и включающий в себя все вершины исходного графа, называется остовом. Число ребер, не вошедших в остов, называется цикломатическим числом. Цикл в графе G ( X, U), длина которого равна Х, называется гамильто-новым циклом, а граф, в котором такой цикл существует, - гамильто-новым графом. [50]

С другой стороны, нетрудно видеть, что x ( G) 1 тогда и только тогда, когда G - вполне несвязный граф, и что X ( G) 2 тогда и только тогда, когда G - двудольный граф, отличный от вполне несвязного графа. G не является вполне несвязным графом, то X ( G) 2 тогда и только тогда, когда G не содержит циклов нечетной длины. В частности, заметим, что любое дерево, имеющее не менее двух вершин, является 2-хроматическим, и то же верно для любого циклического графа с четным числом вершин. [51]

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

Граф, для которого х. 2, К3 и 64. [53]

Проверим сначала второе неравенство. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. [54]

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

Следовательно, класс изоморфизма графа Д определяется однозначно. Если подграфы Н вводятся как компоненты несвязного графа Н, то граф / С изоморфен Я. [56]

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