Cтраница 3
Рассмотрите задачу отыскания кратчайших путей из всех узлов сети общего вида, содержащей р узлов, в конечный узел. Предположим, что эти кратчайшие пути являются единственными. Упростите структуру сети, исключив из нее все дуги, не принадлежащие ни одному из найденных путей. Поясните, почему в результате получится связная сеть, почему сна не содержит контуров и почему в ней имеется ровно р - 1 дуг. [31]
Пусть G - подграф сети Г ( а, Ь), содержащий хотя бы одно ребро. Тогда вершина подграфа G называется граничной, если она либо является полюсом, либо инцидентна некоторому ребру сети, не принадлежащему подграфу G. Подграф сети называется отростком, если он обладает единственной граничной вершиной. Подсетью двухполюсной сети называется ее подграф, имеющий ровно две граничные вершины. Эти вершины называются полюсами подсети. Сеть Г ( а, b, G) называется связной, если ее граф G является связным. Тривиальной называется двухполюсная связная сеть, имеющая одно ребро. Связная сеть называется сильно связной, если через каждое ребро проходит цепь. [32]
Пусть G - подграф сети Г ( а, Ь), содержащий хотя бы одно ребро. Тогда вершина подграфа G называется граничной, если она либо является полюсом, либо инцидентна некоторому ребру сети, не принадлежащему подграфу G. Подграф сети называется отростком, если он обладает единственной граничной вершиной. Подсетью двухполюсной сети называется ее подграф, имеющий ровно две граничные вершины. Эти вершины называются полюсами подсети. Сеть Г ( а, b, G) называется связной, если ее граф G является связным. Тривиальной называется двухполюсная связная сеть, имеющая одно ребро. Связная сеть называется сильно связной, если через каждое ребро проходит цепь. [33]