Неориентированные графы

[germ9c]

Показать , что в любом графе без петель и кратных ребер , содержащем не менее двух вершин, найдутся две вершины с одинаковыми степенями . (степень вершины графа определяется числом инцидентных этой вершине ребер

[Sonic86]

Это простая задача. Каковы Ваши мысли? Подумайте.

[germ9c]

Sonic86 в сообщении #784691 писал(а):

Это простая задача. Каковы Ваши мысли? Подумайте.

извините, но вообще не имею представления , как решать такую задачу

[Sonic86]

germ9c в сообщении #784694 писал(а):

извините, но вообще не имею представления , как решать такую задачу

Ну, пичально, что сказать. В нашем обычном универе в методичке по графам это была первая задачка.
Подумайте, что особого в графе, у которого все вершины имеют разную степень инцидентности, попытайтесь построить такой граф для некоторых $n$. Почему не получается?

[provincialka]

Попробуйте от противного. Вот, вы построили граф с $n$ вершинами, у всех вершин разные степени. Какие они могут быть? Попробуйте построить граф с такими свойствами.

[VAL]

А я предложу начать с еще более простого вопроса:
Допустим у графа $n$ вершин. В каком диапазоне может находится степень некоторой его вершины?

[germ9c]

VAL в сообщении #784753 писал(а):

А я предложу начать с еще более простого вопроса:
Допустим у графа $n$ вершин. В каком диапазоне может находится степень некоторой его вершины?

от 1 до (n-1)

[arseniiv]

Почему 1, а не 0? О связности графа ничего не сказано, вершина может быть изолированной.

И итого получается столько же различных степеней вершин, сколько вершин. Как теперь можно переформулировать то, что надо доказать?

[germ9c]

germ9c в сообщении #784687 писал(а):

Показать , что в любом графе без петель и кратных ребер , содержащем не менее двух вершин, найдутся две вершины с одинаковыми степенями . (степень вершины графа определяется числом инцидентных этой вершине ребер

значит набор точек, некоторые пары которых соединены линиями, причем одна пара вершин не может быть соединена более чем одной линией. И значит найдутся две вершины с одинаковыми степенями

[arseniiv]

Что-то не то. Вы не описали, как именно следует, и никак не использовали число возможных кратностей.

-- Вт ноя 05, 2013 02:07:40 --

Ну вот пускай у каждой вершины своя кратность — их же поровну. У первой — 0, у второй — 1, …, у последней, $n$-й — $n-1$. И будет всё хорошо. Или не будет? А почему?

[VAL]

germ9c в сообщении #784796 писал(а):

значит набор точек, некоторые пары которых соединены линиями, причем одна пара вершин не может быть соединена более чем одной линией.

Это где так графы определяют? Если в третьем классе, то все в порядке!
Но студентов я за такие определения...
Не буду даже говорить, что я с ними делаю. Тем более, что все равно бесполезно

[bot]

(Оффтоп)

VAL в сообщении #784802 писал(а):

Не буду даже говорить, что я с ними делаю. Тем более, что все равно бесполезно

Почему бесполезно? В порядке обмена опытом очень даже полезно бы узнать, что это такое Вы с ними делаете?

[VAL]

(Оффтоп)

bot в сообщении #785155 писал(а):

VAL в сообщении #784802 писал(а):

Не буду даже говорить, что я с ними делаю. Тем более, что все равно бесполезно

Почему бесполезно? В порядке обмена опытом очень даже полезно бы узнать, что это такое Вы с ними делаете?

Сразу скажу: ничего противозаконного
Но, возможно, зря. Ибо законные методы бессильны.

Вот, например, история этого года.
1. Когда рекомендовал литературу, специально посмотрел, чтобы во всех книжках графы определялись как теоретико-множественные объекты, а не через точки и линии (как, например, в известной книжке Березиной).
2. Дал определение и сразу привел пример графа перечислением вершин и ребер, без всякой картинки.
3. Ввел простейшие понятия (инцидентность, смежность, степень вершины), сознательно не прибегая к картинке.
4. Привел другой пример: графа знакомств. Подчеркнул, что вершины - это люди, а ребра вообще никак не проявляются внешне.
5. Позже, конечно, не удержался, дал геометрическую интерпретацию. Но на каждом последующем занятии обязательно напоминал, что, изображение графа, хотя и несет о нем всю необходимую информацию, не есть сам граф.

И что? На экзамене девушка, которая не пропустила ни одной пары, сидела на первой парте и все записывала. Да что там записывала?! Слушала (сам видел)! Так вот, этой девушке достается вопрос "определение графа". И она радостным голосом (повезло же - вопрос легкий!) отвечает: "Графом называется совокупность точек и соединяющих их линий..."

[provincialka]

(Оффтоп)

нут что такого страшного, если человек может поавильно пользоваться понятием. Не надо быть такими пуристами

[VAL]

(Оффтоп)

provincialka в сообщении #785197 писал(а):

нут что такого страшного, если человек может поавильно пользоваться понятием. Не надо быть такими пуристами

Первое, что огорчает в подобной ситуации - это полное бессилие хоть как-то на что-то повлиять.

Теперь про пуризм.
При таком понимании, чаще всего и умение пользоваться соответствующее.
Студенты, о которых идет речь - информатики. Графы нужны им не для общего развития, а для последующей реализации важных алгоритмов.
И как студент, понимающий графы подобным образом, будет реализовывать эти алгоритмы? Да что там, как он будет вводить графы в память компа?
Вы спрашивали? Я спрашивал. Хотя ответ очевиден... Правильно! Нарисую картинку и отсканирую".