Несвязный граф
Cтраница 3
Здесь Sj и S z - подматрицы инциденций, соответствующие связным компонентам несвязного графа. [31]
Разрез связного графа - это множество ребер, удаление которых приводит к несвязному графу. Коциклом называется минимальный разрез. Кограницей графа G называется кограница некоторой его 0-цепи. Кограница набора U вершин есть не что иное, как множество всех ребер, соединяющих вершины из U с вершинами, не принадлежащими U. Очевидно, что каждая кограница является разрезом. Поскольку коцикл определяется как минимальный разрез графа G, а любой минимальный разрез есть кограница, то всякий коцикл является минимальной ненулевой кограницей. [32]
Если удалить / г ребер, соединяющих вершины из Ci с вершинами из DI, получим несвязный граф. [33]
Числом вершинной связности % ( G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному графу. Числом реберной связности ЦС) графа G называется наименьшее число ребер, удаление которых приводит к несвязному графу. [34]
Минимальное число вершин ( и соединяющих их ребер) графа G, удаление которых из О приводит либо к несвязному графу, либо к тривиальному графу с одной вершиной; в случае k - связных графов должно быть удалено, по меньшей мере, k вершин. [35]
С другой стороны, нетрудно видеть, что x ( G) 1 тогда и только тогда, когда G - вполне несвязный граф, и что X ( G) 2 тогда и только тогда, когда G - двудольный граф, отличный от вполне несвязного графа. G не является вполне несвязным графом, то X ( G) 2 тогда и только тогда, когда G не содержит циклов нечетной длины. В частности, заметим, что любое дерево, имеющее не менее двух вершин, является 2-хроматическим, и то же верно для любого циклического графа с четным числом вершин. [36]
 |
Независимые, но нефундаментальные циклы. [37] |
Таким образом, остовный подграф 6 ( X, А - ( Х0, Х0)), полученный из С удалением ребер, принадлежащих разрезу, является несвязным графом, состоящим ао крайней мере из двух компонент. [38]
Любая пара вершин графа G может быть соединена по крайней мере п вершинно непересекающимися цепями тогда и только тогда, когда в нем существует п вершин, удаление которых приводит к несвязному графу. [39]
С другой стороны, нетрудно видеть, что x ( G) 1 тогда и только тогда, когда G - вполне несвязный граф, и что X ( G) 2 тогда и только тогда, когда G - двудольный граф, отличный от вполне несвязного графа. G не является вполне несвязным графом, то X ( G) 2 тогда и только тогда, когда G не содержит циклов нечетной длины. В частности, заметим, что любое дерево, имеющее не менее двух вершин, является 2-хроматическим, и то же верно для любого циклического графа с четным числом вершин. [40]
Докажите, что всякий критический граф, являющийся fe-xpo - матическим, обладает следующими свойствами: ( i) он связен; ( ii) степень каждой его вершины не меньше k - 1; ( Hi) не существует вершины удаление которой приводит к несвязному графу. [41]
Если граф имеет вершины, которые нельзя соединить цепью со всеми остальными вершинами, такой граф называют несвязным. Несвязный граф распадается на несколько изолированных частей, называемых связными компонентами графа. На рис. 1 - 7 показан несвязный граф, состоящий из трех связных компонент. [42]
Связный граф называется разделимым или неразделимым в зависимости от того, имеет он или не имеет 1-разделение. Всякий несвязный граф удобно считать разделимым. [43]
 |
Деревья графа.| Неплоские графы. [44] |
Если исходный граф является несвязным, то деревья образуются для каждой несвязной части графа. Совокупность деревьев несвязного графа называют лесом этого графа, формула (2.58) справедлива и для несвязного графа с общим количеством ветвей пв, если яд и тгх - общее число ветвей и хорд деревьев в лесу. [45]
Страницы: 1 2 3 4