2014 dxdy logo

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

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


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


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



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


03/02/19
138
Тогда не думаю, что так проще. "Цикл длины больше 3" откуда появился?

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


22/01/11
2641
СПб
Данное
situs в сообщении #1383810 писал(а):
Доказательство. Предположим, наоборот, что существует граф, который не содержит $G_1$ и не является объединением изолированных вершин и полного дву- или трехдольного графа.

Это действительно не так. Можно начать строить с одной вершины. И будем получать либо тривиально множество изолированных вершин. Либо, если добавляется ребро, какой-то из трех графов: полный двудольный, полный трехдольный и граф содержащий $G_1$.

явно уступает по ясности доказательству Geen

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


03/02/19
138
alcoholist в сообщении #1383986 писал(а):
явно уступает по ясности доказательству Geen
Это вопрос вкусов и предпочтений. К тому же не понятно откуда "циклы длины больше 3".
А допустим я использую это утверждение в работе не по теории графов. Тогда мне нужно дополнительно к понятию графа определять понятия "смежности, пути, цикла, дерева" ...

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


27/04/09
28128
Зачем определять — они общеприняты, если речь о графах.

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


22/01/11
2641
СПб
situs в сообщении #1383810 писал(а):
Предположим, наоборот, что <...>
Это действительно не так.

Если честно, то звучит коряво. Вроде бы от противного, а вроде бы и нет.

situs в сообщении #1383995 писал(а):
Тогда мне нужно дополнительно к понятию графа определять понятия "смежности, пути, цикла, дерева" ...

В вашей формулировке фигурируют куда более продвинутые понятия дву- и трехдольных графов.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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