Простой граф

Cтраница 3

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

Докажите также, что простой граф изоморфен своему реберному графу тогда и только тогда, когда он является регулярным степени 2, и опишите все такие графы. [32]

Доказать, что если простой граф G с четным числом вершин р содержит больше, чем ( р г) ребер, то он имеет совершенное паросочетание. [33]

Доказать, что в простом графе каждое наименьшее Т - соединение является лесом, причем каждая компонента этого леса - индуцированный подграф. [34]

Выше были рассмотрены так называемые простой граф и смешанный граф. Однако существуют графы, содержащие только дуги. В качестве примера приведем орграф ( рис. 1 - 13, г), направление и вес дуг которого отображают направление и значение тока ветвей электрической схемы, показанной на рис. 1 - 13, а. Подобные орграфы применяются в алгоритмах автоматического составления уравнений на ЭВМ. [35]

Дополнением G графа G называется простой граф с множеством вершин V ( G), в котором две вершины смежны тогда и только тогда, когда они не смежны в G. Заметим, что дополнение полного графа является вполне несвязным графом и наоборот; дополнение регулярного графа регулярно. [36]

Исходя из булева матричного представления простого графа, можно определить покрытие как такой набор единиц, что каждая строка и каждый столбец матрицы содержат по крайней мере по одному элементу из этого набора. [37]

I являются наборами степеней вершин простых графов. [38]

Граф ресурсов ( а. цикл, извлеченный из а ( б. [39]

Несмотря на то что в простом графе относительно легко зрительно различить взаимоблокировку процессов, для использования такой схемы в настоящей системе нам необходим формальный алгоритм, выявляющий тупики. [40]

Докажите, что если в простом графе О, имеющем п ( 3) вершин, для каждой пары а и w несмежных вершин р ( v) р ( т) п, то G является гамильтоновым графом. [41]

Доказательство теоремы 7.4.1. Пусть С - простой граф с максимальной степенью k - L Покажем, используя индукцию по V ( G), что G является реберно - раскрашиваемым. Следовательно, при выбранной fc - раскраске в каждой из них будут отсутствовать не менее двух цветов. Применяя лемму 7.4.2, заключаем, что граф G является реберно - раскрашиваемым. [42]

Доказать, что если G - простой граф с максимальной степенью k и каждый цикл в нем проходит через вершину степени не выше k - 1, то граф G реберно - раскрашиваемый. Мы думаем, что в этом упражнении достаточно ограничиться нечетными циклами. [43]

Подчеркнем тот факт, что каждый простой граф является графом, но не каждый граф является простым графом. [44]

Докажите, что если G - простой граф, то ( i) G и G не могут одновременно быть несвязными; ( ii) из того, что G связен, следует, что реберный граф L ( G) тоже связен. [45]

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