11.4. операции над графами

11.4. операции над графами: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.

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 не содержит циклов и при соединении ребром произвольных двух его несмежных вершин получается граф, имеющий, ровно один цикл,

Справочник по математике для экономистов

Справочник по математике для экономистов

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

11.4. операции над графами: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.