Множество - ребро
Cтраница 2
Множество ребер связного графа, после удаления которых граф становится несвязным. [16]
Если множество ребер, инцидентных некоторой вершине и связного графа, не является простым разрезом, то удаление этих ребер делит граф по меньшей мере на 3 компоненты. Но тогда v есть точка сочленения. [17]
Это множество ребер, исходящих из вершин j3 ( ( г - 1 ш - 1), назовем правой предикатной частью. [18]
Это множество ребер, исходящих из вершин f3 ( ( г 1 га - 1), назовем правой предикатной частью. [19]
Вначале множество ребер триангуляции является пустым. Основной шаг процедуры триангуляции включает следующие действия. В пуле выбирается и исключается из него ребро наименьшей длины. Если это ребро не пересекает ни одно из ребер, уже вошедших в триангуляцию, то оно также включается в число ребер триангуляции. Иначе ребро просто исключается из дальнейшего рассмотрения. [20]
Разбиение множества ребер, инцидентных вершине v в графе G, при их распределении по новым вершинам осуществляется произвольно, - нужно обращать внимание только на степени новых вершин. [21]
Проведение множества ребер U во внутренней области выпуклой фигуры и множества ребер 1 / 2 во внешней области пересечений не дают. Множество ребер U3 содержит п - 3 ребра, а так как каждое пересечение образуется наложением двух ребер, то ребра множества 1 / 3, проведенные во внутренней области, пересекаясь с ребрами множества 1 / ь образуют С2п 3 пересечений. Так как множество ребер, инцидентных вершине 4, расположенных во внешней области, содержит п - 4 ребра, то ребра множества 1 / 4, пересекаясь с ребрами множества U2, образуют С2 - пересечений. Наличие постоянного коэффициента объясняется тем, что множества ребер l / s и 1 / 6 пересекаются с двумя другими множествами, расположенными в той же области. [22]
В - множество ребер, каждое из которых определяется своим весом. [23]
G называется множество ребер, покрывающее каждую вершину ровно один раз. В работе [1] показано, что если число ребер графа G превосходит ( Vs ft2, где с 0, то граф G не может иметь единственное паросочетание. Метод доказательства опирается на результат Жнама. Этот результат позволяет находить в графе G непересекающиеся полные подграфы G; типа ( г г), где rc logn, такие, что, добавляя ребра, можно расширить каждое паросочетание графа 2 GI ДО паросочетания графа G. В настоящей статье мы покажем, что для этого достаточно найти подграф графа G, ребра которого распределены с некоторой регулярностью, и получим для числа паросочетаний лучшие оценки. [24]
Доказать, что множество ребер, определенных в предыдущем абзаце, образует паросочетание. [25]
Сечением сети называется множество ребер, при удалении которого сеть становится несвязной, причем полюсы попадают в разные компоненты связности. Ясно, что каждая цепь ( а тем более каждый путь из ая в 3 s) проходит хотя бы через одно ребро сечения. Сечение будем называть простым, если при удалении любого его ребра, оно перестает быть сечением. Так, d, е, / и ( 6, с, е, g, h являются простыми сечениями, в то время как [ d, g, h, i не является таковым. Очевидно, что для каждого ребра простого сечения можно указать цепь, которая проходит через это ребро, но не проходит через другие ребра данного сечения. [26]
 |
Дерево с цветком. [27] |
Хо, то множество ребер [ Р У Р - Р П Р вместе с ребром ( х 0, х) образует цветок. На рис. 12.7 изображено цветущее дерево. [28]
 |
Механическая цепь ( а и ее граф, представленный в двух конфигурациях ( б и в. [29] |
Сечением называют такое множество ребер связного графа, удаление которого Делит исходный граф на два изолированных подграфа. Следовательно, сечение представляет собой разделение вершин графа. Однако могут быть и такие сечения, которые нельзя показать, не придав графу другой конфигурации. Важными являются также понятия неразделимых, пленарных и дуальных графов. Граф называют неразделимым, если каждый подграф графа имеет минимум две вершины, общие с его дополнением. Неразделимый граф соответствует неразделимой цепи. [30]
Страницы: 1 2 3 4