Свойства объединения двух связных графов, если их пересечение не связно

Question

Пусть G1=(V, E1)and G2=(V, E2) - связные графы на одном и том же множестве вершин V с более чем двумя вершинами.Если G1∩G2=(V, E1∩E2) не является связным графом, то у графа G1∪G2=(V, E1∪E2)

a) не может быть вырезанной вершины.

b) должен быть цикл

c)должен иметь режущий край (мост)

d) Имеет хроматическое число строго больше, чем у G1 и G2

=========================================================================

Правильный ответ - вариант (б)

========================================================================

Мой подход такой:

Дело в том, что я получаю вариант а) и исправьте способ выбора графика.Итак, как я могу быть уверен в экзамене, какой график взять, чтобы я получил правильный ответ, как вы можете видеть здесь, правильный ответ - вариант б), но я также получаю а) правильный.

Answer 1

Чтобы на самом деле доказать, что G1 2 G2 содержит цикл.

Необходимо рассмотреть два случая, сначала тривиальный случай:

Если в G1 или G2 содержится цикл, то G1 ∪У G2 должен быть цикл - цикл, который существовал в G1 или G2.

Более интересный случай, когда и G1, и G2 являются ациклическими.

Некоторые (надеюсь) уже установили факты о любых связанныхациклический неориентированный граф G = (V, E):

• Существует ровно 1 путь между каждой парой вершин (V1 ∈ V, V2 ∈ V), V1 ≠ V2.
• | E |= | V |- 1.

Так что для G1 и G2 оба являются ациклическими и связными, они оба содержат | V |- 1 ребро.Поскольку G1 ∩ G2 не связно, они не должны быть G1 = G2, в G2 должно быть ребро, которого не существует в G1.

Рассмотрим это ребро Ek = (Vi, Vj) так, чтобы(Vi, Vj) ∉ E1 и (Vi, Vj) ∈ E2

Граф G1 ∪ G2 содержит путь из Vi в Vj, который находится в G1, поскольку он содержит все ребра в G1.Поскольку G1 еще не содержит Ek, включая его (из G2), создается цикл, включающий путь от Vi до Vj в G1 и ребро Ek, поэтому G1 ∪ G2 должен содержать цикл.

Answer 2

Если ваша цель состояла в том, чтобы опровергнуть контрпримером, то вы получили хорошее начало с простого графика с 3 вершинами.

Такой график соответствует требованиям, что G1 и G2 связаны, а пересечение не связано.Тем не менее, союз только опровергает ответ в).В частности, объединение

• не имеет обрезанной вершины, поэтому a) имеет значение разрешено
• имеет цикл, поэтому b) разрешено
• не имеет режущей кромки, поэтому в) исключено
• имеет хроматическое число 3, тогда как G1 и G2 имеют хроматическое число 2, поэтому d) имеет значение разрешено

Следующим шагом является осознание того, что d) почти наверняка не так.Причина: легко добавить узлы в график без изменения его хроматического числа.То есть, должно быть легко найти пример, где G1 и G2 трехцветные, а объединение также трехцветное.

Так что у вас останется а) или б).
Если вы предполагаете, что а) неверно, то вам нужно найти граф, который имеет вырезанную вершину и имеет цикл.
Если вы предполагаете, что b) неверно, то вам нужно найти график, который не имеет обрезанную вершину и не имеет цикл.

Гаданието, что b) неверно, немного проблематично, потому что граф без циклов - это дерево или путь , а деревья и пути полны срезанных вершин.

Итак, следующий шаг - представить граф, у которого есть отрезанная вершина.Первый такой график, который пришел ко мне, это песочные часы:

Еще раз, G1 и G2 соединены, а пересечение не соединено.На этот раз профсоюз опровергает три ответа.В частности, у объединения

• есть вершина среза, поэтому a) имеет значение исключено
• имеет цикл, поэтому b) разрешено
• не имеет режущей кромки, поэтому в) исключено
• имеет хроматическое число 3, а G1 и G2 также имеют хроматическое число 3, поэтому d) исключено

Обратите внимание, что мы не доказали b) верно, только то, что а) в) и г) определенно неверны, поэтому б) ответ отстранением.