2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Неориентированные графы
Сообщение04.11.2013, 18:27 


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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 18:38 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 18:51 


11/04/13
125
Sonic86 в сообщении #784691 писал(а):
Это простая задача. Каковы Ваши мысли? Подумайте.

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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 18:58 
Заслуженный участник


08/04/08
8562
germ9c в сообщении #784694 писал(а):
извините, но вообще не имею представления , как решать такую задачу
Ну, пичально, что сказать. В нашем обычном универе в методичке по графам это была первая задачка.
Подумайте, что особого в графе, у которого все вершины имеют разную степень инцидентности, попытайтесь построить такой граф для некоторых $n$. Почему не получается?

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 21:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 21:36 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 22:49 


11/04/13
125
VAL в сообщении #784753 писал(а):
А я предложу начать с еще более простого вопроса:
Допустим у графа $n$ вершин. В каком диапазоне может находится степень некоторой его вершины?

от 1 до (n-1)

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 22:53 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 22:59 


11/04/13
125
germ9c в сообщении #784687 писал(а):
Показать , что в любом графе без петель и кратных ребер , содержащем не менее двух вершин, найдутся две вершины с одинаковыми степенями . (степень вершины графа определяется числом инцидентных этой вершине ребер

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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 23:06 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение04.11.2013, 23:12 
Заслуженный участник


27/06/08
4063
Волгоград
germ9c в сообщении #784796 писал(а):
значит набор точек, некоторые пары которых соединены линиями, причем одна пара вершин не может быть соединена более чем одной линией.
Это где так графы определяют? Если в третьем классе, то все в порядке! :-)
Но студентов я за такие определения...
Не буду даже говорить, что я с ними делаю. Тем более, что все равно бесполезно :-(

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение05.11.2013, 17:47 
Заслуженный участник
Аватара пользователя


21/12/05
5932
Новосибирск

(Оффтоп)

VAL в сообщении #784802 писал(а):
Не буду даже говорить, что я с ними делаю. Тем более, что все равно бесполезно :-(

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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение05.11.2013, 18:22 
Заслуженный участник


27/06/08
4063
Волгоград

(Оффтоп)

bot в сообщении #785155 писал(а):
VAL в сообщении #784802 писал(а):
Не буду даже говорить, что я с ними делаю. Тем более, что все равно бесполезно :-(

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

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

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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение05.11.2013, 18:58 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань

(Оффтоп)

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

 Профиль  
                  
 
 Re: Неориентированные графы
Сообщение05.11.2013, 19:32 
Заслуженный участник


27/06/08
4063
Волгоград

(Оффтоп)

provincialka в сообщении #785197 писал(а):
нут что такого страшного, если человек может поавильно пользоваться понятием. Не надо быть такими пуристами
Первое, что огорчает в подобной ситуации - это полное бессилие хоть как-то на что-то повлиять.

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

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

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



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

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


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

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