Подграф - граф
Cтраница 2
Подграфом графа G ( V, а) называется граф С. [16]
 |
Помеченные и непомеченный графы.| Граф и два его подграфа. [17] |
Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G. Если Gt - подграф графа G, то G называется подграфом ( supergraph) графа GJ. Остовный подграф - это подграф J) графа G, содержащий все его вершины. Таким образом, две вершины из 5 смежны в S тогда и только тогда, когда они смежны в G. На рис. 2.6 G2 - остовный подграф графа G, a Gr нет; d - порожденный подграф, a G2 нет. [18]
Подграфом графа G называем граф, у которого все вершины и ребра принадлежат G. Подграф, содержащий все вершины графа, называем остовным подграфом. Для любого подмножества S вершин графа G порожденным подграфом ( обозначается G ( S)) называется максимальный подграф графа G, множеством вершин которого является S. Vi-i, y -) VieAfn, причем все ребра различны. Если в цепи УО УП) то цепь называется циклом. Если различны все вершины цепи, то L называем простой цепью, если при этом v0 vn, то L называем простым циклом. Граф G называется связным, если между любыми двумя его вершинами существует простая цепь. Две простые цепи между вершинами и и v называются вершинно непересекающимися, если у них нет общих вершин, отличных от v и и. Граф G называется d - связным графом, если между каждой парой его верш ш существует а вершинно непересекающихся цепей. [19]
Рассмотрим подграф Сг графа G - Го, для которого С П Н ф 0 и который является компонентой графа G - Т для некоторого наименьшего разделяющего множества вершин Т графа G. Такие подграфы существуют по предположению; пусть, С - такой подграф с минимальным числом вершин и Т - соответствующее наименьшее разделяющее множество вершин. Если в С П Я найдется вершина с, для которой N ( c H) T, то предложение доказано. Поэтому предположим, что в СПЯ существует ребро с, с7, с е Г, и покажем, что это предположение приводит к противоречию. Тем самым предложение 1 будет доказано. [20]
Максимальные сильно связные подграфы графа на рис. 95 обведены пунктиром. [21]
Два подграфа графа О называются реберно непересекающимися, если они не имеют общих ребер. [22]
Пусть каждый конечный подграф счетного графа G fe-pac - крашиваем; докажите, что Отожей-раскрашиваем, и выведите отсюда, что каждый счетный пленарный граф 5-раскрашиваем. [23]
Если Н - подграф графа О, то мы, естественно, считаем, что дуги, ассоциированные с ребром Е в подграфе Я, совпа-падают с соответствующими дугами из О. [24]
Пусть С - подграф графа С ( М), являющийся объединением трех внутренне непересекающихся цепей / ь Ь2 и Ь3 с общими концами х и у. Тогда подграф С ( М): ( Е ( М) - - Е ( С)) графа 0 ( М) имеет только три компоненты: Н, Н2 и Н3, причем эти компоненты являются остаточными графами циклов Ь2 11 Ьз, ЕЗ У 1 и Ь У Ь2 соответственно. [25]
Цепь Ь есть подграф графа С, и соединяющими вершинами у нее являются только х и у. Значит, по теореме I. Если относительно С найдется второй мост, то теорема справедлива. Если же относительно С второго моста нет, то О, будучи объединением трех внутренне непересекающихся цепей 1, Ь и N, является тэта-графом. [26]
Пусть Н - подграф графа О, определяемый вершиной х, инцидентными ей ребрами и другими концами этих ребер. Тогда пара ( Н, Яс) является п-разделением графа С для некоторого целого положительного п уа. [27]
 |
Если произвольный граф не планарен. [28] |
Поэтому мы получаем подграф Куратовского графа О. Тем самым доказательство в двусвязном случае завершено. [29]
Если Н - подграф графа G, то G называется надграфом графа Я. Вместо утомительной фразы корневые графы G, у которых в качестве корня берется подграф Я, не обязательно являющийся порожденным подграфом, мы предпочитаем говорить над-графы графа Я, что обеспечивает более эффективную мнемоническую схему. [30]
Страницы: 1 2 3 4