Спирина, М.С. Дискретная математика

Подграфом графа G={V, X) назы­ вается граф Gy=(Vy, Хх), все вершины и ребра которого являются подмно­ жествами множества вершин и ребер графа G. Обозначения такие же, как и для множеств: Gy с G, если Kj с К, Хх с X. Отметим, что не любая пара (К,, ЛГ,), где V, с V, Хха X, будет яв­ ляться подграфом. Для этого еще не­ обходимо, чтобы она являлась графом, т.е. Xya{(Vh Vj) | Vh V/E Vy}. В против­ ном случае у подграфа могло появить­ ся ребро, не инцидентное ни одной его вершине. Кольцевой суммой двух графов называется граф G = Gy ф G2, порожденный множеством вершин К= К, U V2 и множеством ребер (A' i U П Х2), т.е. множеством ребер, содержащихся либо в Gy, либо в G2, но не в (7,П G2. Пусть графы Gy и G2 имеют вид, представленный на рис. 2.12, а, б. Тогда их объединением, пересечением и кольцевой суммой будут соответственно графы G, G' и G" (рис. 2.12, в, г, д). Напомним, что компонентой связности неориентированного гра­ фа G(V, X) называется его подграф G' ( К', X) с множеством вершин V’ <= Ки множеством ребер X, инцидентных только верши­ нам из множества К', причем ни одна вершина из V,e V не смеж­ на с вершинами из множества V П К Тогда несвязный граф со­ стоит из нескольких отдельных подграфов — компонент связности, т.е. связных графов. Например, несвязный граф G (рис. 2.13) со­ стоит из двух компонент связности, т. е. из двух подграфов G' и G". G G" G’ Рис. 2.13. Несвязный граф G с двумя компонентами связности G' и G" 2.3. Деревья. Лес. Бинарные деревья С вершины дорога вперед —только вниз. П. Таранов Деревом называют конечный связный граф с выделенной вер­ шиной (корнем), не имеющий циклов (рис. 2.14). Для каждой пары вершин дерева — узлов — существует един­ ственный маршрут, поэтому вершины удобно классифицировать по степени удаленности от корневой вершины. Расстояние до кор­ невой вершины К0 называется ярусом s вершины, s=d(V0V). Поскольку маршрут между двумя вершинами единственный, то, применяя это свойство к смежным вершинам, можно заклю­ чить, что любая ветвь является мостом. Действительно, при уда­ лении ребра этот единственный маршрут прерывается. Тогда граф 80