Подграф - граф
Cтраница 3
Ясно, что подграф графа G, содержащий остов Т и его произвольную хорду, имеет только один ( простой) цикл. Множество Z ( T) всех таких циклов ( каждая хорда порождает один цикл) независимо, так как каждый из них содержит ребро, не принадлежащее ни одному из остальных циклов. Более того, любой цикл Z зависит от множества Z ( T), причем Z есть симметрическая разность циклов, которые определяются хордами остова Т, принадлежащими Z. Поэтому, определяя циклический ранг m ( G) как число простых циклов базиса пространства циклов графа G, можно сформулировать следующий результат. [31]
Напомним, что подграф G графа G называется эластичным, если граф G - V ( G имеет совершенное паросочетание. [32]
Пусть G - эластичный элементарный подграф графа G, содержащий Go и имеющий наименьший размер среди подграфов с таким свойством. [33]
Рассмотрим класс всех подграфов графа G, содержащих простой цикл, составленный самое большее из двух геодезических линий и внутренних по отношению к этому циклу вершин и ребер. Легко видеть, что минимальные по числу вершин элементы этого класса будут неприводимыми линзами. [34]
Еэк как 6 - подграф графа G, то и все цепи графа, соедазяющие вершины У и У, проходят через вершины цикла С Следовательно, цикл С ив графе ( J является внут - Ренгош. Остается доказать что щкл ( 2 делит граф & & на два треховязных подграфа. [35]
 |
Граф G ( f. [36] |
Графом предиката f называется подграф графа Коп ( 2, 3), порожденный множеством вершин, соответствующих конституентам единицы предиката. [37]
Пара Я, К подграфов графа О называется комплементарной, если каждый из подграфов Я и К является расширенным дополнением другого в графе О. [38]
Теорема 1.5. Всякий подграф произвольного подграфа графа С является подграфом графа О. [39]
Известен ряд - реберных стягиваемых подграфов графа G; это число способов выбора К ребер из множества ребер графа G. И число несвязных подграфов оказывается реконструируемым с помощью расширенной нами леммы Кэли. Существует аналогичная теория, рассматривающая вместо несвязных сепарабельные ( но связные) графы. [40]
Qi) будем называть подграфом графа G тогда и только тогда, когда выполняются следующие условия. [41]
Пусть Я и К - подграфы графа С; через ( 2 ( С; Я, / С) обозначим множество всех вершин х из О, которые содержатся и в ИГ ( С, Я), и в Г ( 0, / С), но не принадлежат 7 ( 0 Н ] К. Вершины х из множества ( 3 ( С Н К) можно охарактеризовать и иначе: каждая из них инцидентна какому-либо ребру из Я, не принадлежащему подграфу К, а также какому-нибудь ребру из К, не принадлежащему подграфу Я, но не инцидентна ни одному из ребер графа О, не содержащихся ни в Я, ни в К. [42]
Обратно, пусть Я - произвольный подграф графа О, а НХи - сжатие этого подграфа. В силу теоремы 1.23 компонентами подграфа Я: 3 являются все компоненты подграфа О: С, содержащиеся в Я. Отсюда следует, что Я X есть подграф сжатия ОХ ( Е ( 0) - ( 2) графа О. [43]
Сг ( G) - двудольные подграфы графа G, не являющиеся сводимыми. [44]
Подграфы Л и G называются несобственными подграфами графа G. Все остальные подграфы графа G называются собственными подграфами. [45]
Страницы: 1 2 3 4