Множество - ребро
Cтраница 3
 |
Два 1-фактора блока. [31] |
Напомним, что множество попарно несмежных ребер называется независимым. Под нечетной компонентой графа G понимается компонента с нечетным числом вершин. [32]
 |
Механическая цепь ( а и ее граф, представленный в двух конфигурациях ( б и в. [33] |
Сечением называют такое множество ребер связного графа, удаление которого Делит исходный граф на два изолированных подграфа. Следовательно, сечение представляет собой разделение вершин графа. Однако могут быть и такие сечения, которые нельзя показать, не придав графу другой конфигурации. Важными являются также понятия неразделимых, пленарных и дуальных графов. Граф называют неразделимым, если каждый подграф графа имеет минимум две вершины, общие с его дополнением. Неразделимый граф соответствует неразделимой цепи. [34]
 |
Двусвязный циклический список ( сдвиги порождают циклическую группу.| Линейный двусвязный список ( сдвиги порождают частичную циклическую группу. [35] |
Полугруппа сдвигов определяется множеством ребер. Пусть yt обозначает / - е ребро, выходящее из вершин. Очевидно, что полугруппа сдвигов в данном случае может быть определенной не на всех элементах из 1 /, так как если v не имеет 1-го ребра, то ъщ не определено. Информация, хранящаяся в вершинах графа, определяет множество значений памяти. [36]
Граф, у которого множество ребер пусто, называется вполне несвязным ( или пустым) графом. [37]
Вдовами конфигурации At служат множества ребер, проходящих через одну и ту же вершину конфигурации. В силу определения конфигурации блоки состоят из трех ребер. [38]
Разделяющее множество представляет собой множество ребер связного графа, после удаления которого граф становится несвязным. Разделяющее множество, состоящее из всех ребер, которые соединяют некоторое множество вершин графа V с его дополнением V ( VJV V, V f V 0), называют разрезом. [39]
Применяя теорему 11.34 к множествам ребер из Р и, Р2, получаем, что Р не является дважды пересеченным. [40]
 |
Иллюстрация некоторых основных понятий и определений теории графов ( путь графа - последовательность однонаправленных различных дуг а, Ь. цепь графа - последовательность различных ребер с, d, e. [41] |
V), и множеством ребер ( дуг) Е сЕ, каждое из которых принадлежит только вершинам из V. Остовное дерево некоторого графа - это его остовный подграф, являющийся деревом. [42]
Носитель такого вектора - это множество ребер, которые находятся под ненулевым напряжением. Элементарный вектор из L-L соответствует напряжению, отличному от нуля в минимальном множестве ребер. [43]
Разрез связного графа - это множество ребер, удаление которых приводит к несвязному графу. Коциклом называется минимальный разрез. Кограницей графа G называется кограница некоторой его 0-цепи. Кограница набора U вершин есть не что иное, как множество всех ребер, соединяющих вершины из U с вершинами, не принадлежащими U. Очевидно, что каждая кограница является разрезом. Поскольку коцикл определяется как минимальный разрез графа G, а любой минимальный разрез есть кограница, то всякий коцикл является минимальной ненулевой кограницей. [44]
W и U 7, множество ребер, соединяющих W с W, называется разрезом. Для любого множества W это множество ребер будет непусто в силу связности графа G, и следовательно, разрез определен. Для любого заданного графа совокупность разрезов, определенных различными множествами W, образует подкласс класса всех разделяющих множеств и, более того, любое разделяющее множество содержит, по крайней мере, один разрез в качестве своего подмножества. [45]
Страницы: 1 2 3 4