2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Неориентированные графы
Сообщение05.11.2013, 19:38 
Аватара пользователя

(Оффтоп)

VAL в сообщении #785234 писал(а):
Вы спрашивали? Я спрашивал. Хотя ответ очевиден... Правильно! Нарисую картинку и отсканирую".
Правда, что ли? Кошмар! На всякий случай спросила у отпрыска, я такие неясности на нем проверяю (7 класс, он как раз в субботу был на кружке в универе, где про графы рассказывали). Конечно, сказал про точки и линии. Но про компьютер ответил правильно, что радует.

 
 
 
 Re: Неориентированные графы
Сообщение06.11.2013, 19:46 
такое доказательство подойдет?

Пусть у графа N вершин. Их степени могут быть числами 0, 1, N-1 (всего N вариантов) Предположим, что вершин с одинаковыми степенями нет. Тогда очевидно, что есть вершина A со степенью 0 (изолированная) и вершина B со степенью N-1 (инцидентная всем остальным, в том числе и вершине A). Но вершина A не может быть никому инцидентна. Противоречие.

 
 
 
 Re: Неориентированные графы
Сообщение06.11.2013, 19:55 
Аватара пользователя
Верно.

Есть еще классическая задача про графы. Собрались шесть человек, некоторые из них дружат друг с другом. Доказать, что обязательно найдется либо три человека, которые попарно дружат, либо три, которые попарно не дружат.

 
 
 [ Сообщений: 18 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group