Связный подграф
Cтраница 1
 |
Деревья графа.| Неплоские графы. [1] |
Связный подграф, содержащий все узлы графа, но не содержащий ни одного контура, называют деревом этого графа. Оставшиеся при этом ветви, называют ветвями дерева, а изъятые ветви - связями ( ветвями связи) графа или хордами этого дерева. Хорды дополняют дерево до полного графа. [2]
Связный подграф, который не принадлежит ни одному большему связному подграфу. [3]
Если остовный связный подграф К графа О имеет остовный блок, то всякий другой блок в К должен быть графом-петлей. Требование отсутствия остовного блока исключает, в частности, случай, когда К является двусвязным графом. [4]
Найти частичный связный подграф ( Мъ NJ) графа ( М, N) так, чтобы М0 с: MI и сумма 1 [ A / J х с IN была минимальна. [5]
 |
Граф ( а и его фундаментальные деревья ( б, в. [6] |
Дерево графа - связный подграф, не имеющий циклов. [7]
Если граф содержит сильно связный подграф, в который заходят по крайней мере две дуги, то такой орграф неаранжируем. [8]
Каждый сегмент - это связный подграф в С-С, но не каждая связная компонента С-С является сегментом, так как два или более сегментов могут иметь общую базовую вершину, как, например, сегменты S3 и S4 на рис. 8.28. Процедура PATH порождает сегменты в порядке убывания их базовых вершин, и все пути одного сегмента порождаются раньше, чем пути следующего сегмента. Ясно, что все пути, принадлежащие сегменту, должны размещаться вместе - либо все внутри С, либо все вне С. Это является причиной объединения путей в сегменты. [9]
Сначала покажем, что любой связный подграф Я связного планарного графа О планарен. [10]
Граф аранжируем, если в каждый сильно связный подграф заходит точно одна дуга. [11]
Деревом связного графа ( схемы) называют связный подграф ( подсхему), содержащий все узлы графа ( схемы), но ни одного контура. [12]
Под компонентой сильной связности понимается произвольный максимальный сильно связный подграф. Показать, что компоненты сильной связности определяют разбиение множества вершин на непересекающиеся непустые подмножества. [13]
С, каждый из которых есть максимальный сильно связный подграф. [14]
Всякий максимальный по включению ( сильно) связный подграф данного графа называется его ( сильной) связной компонентой или ( сильной) компонентой связности. [15]
Страницы: 1 2 3 4