2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Графы (одно доказательство)
Сообщение22.03.2019, 22:51 
Аватара пользователя


03/02/19
138
Доброго времени суток!

Доказываю следующее утверждение: если граф не содержит ни одного из графов $G_1, G_2, G_3, G_4$ (см. рисунок, верхний ряд), то граф является объединением изолированных вершин и полного дву- или трехдольного графа.

Доказательство от противного. Предположим, что существует граф который не является объединением изолированных вершин и полного дву- или трехдольного графа и не содержит ни одного из графов $G_1, G_2, G_3, G_4$.

Далее я показываю (на рисунке под первым рядом), что такого не может быть (см. рисунок). Начинаю рассматривать с минимального графа, то есть с одной вершины (изолированной) и далее добавляю вершины и ребра. В итоге получается, что это либо дву- или трехдольный граф с изолированными вершинами (множество изолированных вершин может быть пустое), либо граф содержащий один из $G_1, G_2, G_3, G_4$.

Посмотрите, пожалуйста. Это же индукция. Хотел бы узнать, как более строго оформить доказательство?

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение22.03.2019, 22:55 
Заслуженный участник
Аватара пользователя


01/09/13
4318
situs в сообщении #1383625 писал(а):
не содержит ни одного из графов $G_1, G_2, G_3, G_4$

А одного графа разве не достаточно?

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение22.03.2019, 22:57 
Аватара пользователя


03/02/19
138
Geen в сообщении #1383627 писал(а):
situs в сообщении #1383625 писал(а):
не содержит ни одного из графов $G_1, G_2, G_3, G_4$

А одного графа разве не достаточно?
Это Вы про $G_3$? Думаю, что не достаточно.

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение22.03.2019, 23:54 
Заслуженный участник


27/04/09
28128
Видимо, про $G_1$ — он содержится в $G_2, G_3, G_4$, так что если в графе не содержится $G_1$, в нём не содержатся и остальные, и тривиально, что если в графе не содержится ни один из них, в нём не содержится и $G_1$, так что условия не содержать $G_1$ и не содержать все четыре эквивалентны.

-- Сб мар 23, 2019 02:06:57 --

Дальше условие переформулируется в «любые два ребра имеют общую вершину», после чего путей добавления рёбер действительно мало, а следствие теоремы можно усилить. (Но достаточно уже и того, что есть?)

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 00:17 
Аватара пользователя


03/02/19
138
arseniiv

Действительно. Спасибо! Правда вторую часть (добавленное Вами сообщение) я не совсем понял. Зачем переформулировать условие? Как это поможет доказательству? Задача поставлена в том виде, который я изначально привел.

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 00:21 
Заслуженный участник
Аватара пользователя


01/09/13
4318
situs в сообщении #1383625 писал(а):
Это же индукция.

А что по поводу $K_{2,2}$?

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 00:35 
Аватара пользователя


03/02/19
138
Geen в сообщении #1383638 писал(а):
situs в сообщении #1383625 писал(а):
Это же индукция.

А что по поводу $K_{2,2}$?
А что с ним не то исходя из
situs в сообщении #1383625 писал(а):
Предположим, что существует граф который не является объединением изолированных вершин и полного дву- или трехдольного графа и не содержит $G_1$

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 00:40 
Заслуженный участник
Аватара пользователя


01/09/13
4318
situs в сообщении #1383643 писал(а):
А что с ним не то

Так он содержит или нет?

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 00:45 
Аватара пользователя


03/02/19
138
Geen в сообщении #1383646 писал(а):
situs в сообщении #1383643 писал(а):
А что с ним не то

Так он содержит или нет?
Он содержит. Так и должно быть.

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 00:57 
Заслуженный участник
Аватара пользователя


01/09/13
4318
situs в сообщении #1383648 писал(а):
Он содержит. Так и должно быть.

Да, спасибо, я просто в порядке уточнения спрашивал - просто Ваша формулировка "теоремы" не очень нравится...

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 01:37 
Аватара пользователя


03/02/19
138
Так что же с индукцией? Как более аккуратно оформить доказательство утверждения?

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 01:47 
Заслуженный участник
Аватара пользователя


01/09/13
4318
situs в сообщении #1383652 писал(а):
Как более аккуратно оформить доказательство утверждения?

Не знаю - мне кажется, что в данном случае более строгое утверждение проще доказать :-)

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 02:08 
Аватара пользователя


03/02/19
138
Какое более строгое утверждение?

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 10:08 
Аватара пользователя


03/02/19
138
arseniiv в сообщении #1383632 писал(а):
Дальше условие переформулируется в «любые два ребра имеют общую вершину», после чего путей добавления рёбер действительно мало, а следствие теоремы можно усилить. (Но достаточно уже и того, что есть?)
Вот чего-то я не понимаю. Может быть "любые два соседних ребра имеют общую вершину"? Переформулируем условие как Вы предлагаете: если в графе любые два ребра имеют общую вершину, тогда он является объединением изолированных вершин и полного ... Что-то не так!

 Профиль  
                  
 
 Re: Графы (одно доказательство)
Сообщение23.03.2019, 10:09 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
situs в сообщении #1383663 писал(а):
"любые два соседних ребра имеют общую вершину"

это тавтология

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 35 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: mihaild


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group