11.4. операции над графами
11.4. операции над графами
Объединением графов Gi = (P1, Ах) и G2 = (P2, Aj) называется граф G~GLjGz, множество вершин которого есть объединение множеств вершин графов GL и G2 (Р = РХ jP2), а множество ребер является объединением множеств ребер этих графов (A = Atj АЛ
Пересечением графов G1 и G2 называется граф G=Glf]G1, множество вершин которого есть пересечение Pi fP2, а множество ребер — пересечение А1сА2.
Кольцевой суммой двух графов называется граф бФ(?2, порожденный на множестве ребер (А1 jA2)(A, (Аг), т. е. на множестве ребер, присутствующих либо в G1; либо в G2, но не принадлежащих их пересечению Gt П G2.
Очевидно, что все эти три операции коммутативны. На рис. 11.5 изображены графы Gv G2, GxjG2, G1f)G2, GX®G2.
11.5. Деревья
Связный граф, не содержащий циклов, называется деревом.
Деревом некоторого графа G называется его связный подграф без циклов. Дерево графа G, содержащее все его вершины, называется остовом графа G или его покрывающим деревом.
Кодеревом Г* остова Т графа G называется такой подграф G, который содержит все его вершины и только те ребра, которые не входят в Т.
На рис. 11.6 представлены граф G, его дерево Gu остов Тх и кодерево Т.
Теорема 11.5. Граф Gen вершинами является деревом тогда и только тогда, когда G-связный граф и число его ребер равно (л-1).
Ребра остова Т называются ветвями графа G, а ребра кодере-ва — Т*-связями.
Теорема 11.6. Граф G является деревом тогда и только тогда, когда G не содержит циклов и при соединении ребром произвольных двух его несмежных вершин получается граф, имеющий, ровно один цикл,
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы