Множество - ребро - граф
Cтраница 3
 |
Значения P ( v. [31] |
По-видимому, случайные графы, в которых ребра независимы, более удобны для применений вероятностных методов анализа. Наиболее известным случайным графом с таким свойством является граф Gn p с п вершинами, в котором каждое из ( 2) возможных ребер входит в множество ребер графа Gn p с вероятностью р независимо от поведения остальных ребер. [32]
Построим неориентированный граф с множеством вершин V и множеством ребер, которое мы определим следующим образом: пусть j G V ( ft); если i - наименьшая вершина в множестве V ( h - 1), смежная с вершиной j в графе G, то тогда ребро х г, j входит в множество ребер строящегося графа. [33]
Заметим, что рассмотренный алгоритм применим для определения планарности мультиграфов. В этом случае вершины графа располагаются, как было предложено выше, а множество ребер графа дополняется фиктивными ребрами так, чтобы образовывался псевдогамильтонов цикл. Теперь, если в результате применения алгоритма окажется, что преобразованный граф планарен, то исходный граф будет заведомо пла-нарным, в противном случае необходимо провести дополнительные исследования. [34]
Предположим, что такого ребра нет. Обозначим через Tz множество всех вершин. Рассмотрим множество ребер графа G, не принадлежащих F. По предположению каждое такое ребро имеет один конец в множестве Т2, а другой - в 7Y Поэтому количество таких ребер, с одной стороны, равно Т2, а с другой - оно не менее 2 Г3), что противоречит неравенству Тг Тъ. [35]
Множество элементов X графа G изображают кружками и называют множеством вершин. Каждую вершину xt e X соединяют линиями с теми вершинами Xj е X, для которых выполняется условие Xj e Fxi. Множество линий, которое соответствует множеству упорядоченных пар вершин ( xt, Xj), где х е X, а х - е Fxit называют множеством ребер графа. Если Xj Ф Xi, то ребро ( х, Xj) изображается линией со стрелкой, которая называется дугой и направлена от xt к Xj. Если Xi Xj, то ребро ( х, х) изображается линией без стрелки, которая соединяет вершину Xi с собой, и называется петлей. [36]
Страницы: 1 2 3