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

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



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

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


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

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