Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Вы спрашивали? Я спрашивал. Хотя ответ очевиден... Правильно! Нарисую картинку и отсканирую".
Правда, что ли? Кошмар! На всякий случай спросила у отпрыска, я такие неясности на нем проверяю (7 класс, он как раз в субботу был на кружке в универе, где про графы рассказывали). Конечно, сказал про точки и линии. Но про компьютер ответил правильно, что радует.
germ9c
Re: Неориентированные графы
06.11.2013, 19:46
такое доказательство подойдет?
Пусть у графа N вершин. Их степени могут быть числами 0, 1, N-1 (всего N вариантов) Предположим, что вершин с одинаковыми степенями нет. Тогда очевидно, что есть вершина A со степенью 0 (изолированная) и вершина B со степенью N-1 (инцидентная всем остальным, в том числе и вершине A). Но вершина A не может быть никому инцидентна. Противоречие.
provincialka
Re: Неориентированные графы
06.11.2013, 19:55
Последний раз редактировалось provincialka 06.11.2013, 19:57, всего редактировалось 1 раз.
Верно.
Есть еще классическая задача про графы. Собрались шесть человек, некоторые из них дружат друг с другом. Доказать, что обязательно найдется либо три человека, которые попарно дружат, либо три, которые попарно не дружат.