Связная сеть

Cтраница 1

Связная сеть Г ( а, Ъ) называется сильно связной, если через каждое ее ребро проходит некоторая цепь. [1]

Связная сеть Г ( а, Ь) является сильно связной тогда и только тогда, когда Г ( а, Ъ) не содержит отростков. [2]

Любая связная сеть К на выпуклой поверхности получается из простейшей сети путем после-довательных добавлений I и II рода. [3]

Направленную двудольную связную сеть без циклов будем называть сетью Кенига, если начала всех дуг принадлежат одному множеству узлов, а концы - другому множеству - узлов и эти множества не пересекатся. [4]

В дальнейшем будем рассматривать только силь. [5]

Пусть теперь связная сеть Г ( а, Ь) не является сильно связной. Покажем, что тогда она содержит отросток. Так как Г ( а, Ь) не является сильно связной, то существуют ребра, через которые не проходит ни одной цепи. В силу связности сети Г ( а, Ь) граф Г обладает по крайней мере одной граничной вершиной. Предположим, что Г имеет по крайней мере две граничные вершины. Пусть с и с - две такие граничные вершины, что указанная цепь АС С не содержит никаких других граничных вершин. [6]

В связной сети не имеет граничных вершин только пустой подграф. Подграф сети называется отростком, если он имеет ровно одну граничную вершину. Ребро сети, через которое не проходит ни одна цепь, называется холостым. [7]

Постройте связную сеть, используя ровно пять дуг. [8]

Следовательно, связная сеть полностью определяется перечислением ее ребер и указанием полюсов. [9]

Если в связной сети удаляется простое сечение, то сеть распадается ровно на две части: левую часть, содержащую as, и правую часть, содержащую Каждое ребро простого сечения связывает вершины из разных частей. Будем называть ребро сечения прямым, если оно в сети не ориентировано или ориентировано слева направо, и обратным - в противном случае. Будет ли ориентированное ребро прямым или обратным, вообще говоря, зависит от выбора сечения. Так, в примере ( см. рис. 8) ребро е в сечениях ( d, е, / и ( Ь, с, е, g, h - обратное, а в сечении ( а, с, е, g, i - прямое. [10]

Множество всех связных сетей ( Г ( а, Ь) вместе с операцией суперпозиции определяет функциональную систему с операцией. [11]

Для того чтобы связная сеть S была сильно связной, необходимо и достаточно, чтобы она не содержала отростков. [12]

Удаление ребра дает связную сеть Г ( я, Ь), но не сильно связную. [13]

Пусть К - некоторая связная сеть на выпуклой поверхности Р, А - один из ее узлов ( черт. Рассмотрим все линии сети, выходящие из узла А ( например, на черт. [14]

Важным частным случаем сети является связная сеть, содержащая р узлов и р - 1 дуг. Сеть такой структуры носит название дерева и не содержит контуров. Нарисуйте на листе бумаги шесть узлов ( р 6), разместив нх случайным образом. [15]

Страницы: 1 2 3