2014 dxdy logo

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

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




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

 
 
 
 Re: Неориентированные графы
Сообщение04.11.2013, 18:38 
Это простая задача. Каковы Ваши мысли? Подумайте.

 
 
 
 Re: Неориентированные графы
Сообщение04.11.2013, 18:51 
Sonic86 в сообщении #784691 писал(а):
Это простая задача. Каковы Ваши мысли? Подумайте.

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

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

 
 
 
 Re: Неориентированные графы
Сообщение04.11.2013, 21:19 
Аватара пользователя
Попробуйте от противного. Вот, вы построили граф с $n$ вершинами, у всех вершин разные степени. Какие они могут быть? Попробуйте построить граф с такими свойствами.

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

 
 
 
 Re: Неориентированные графы
Сообщение04.11.2013, 22:49 
VAL в сообщении #784753 писал(а):
А я предложу начать с еще более простого вопроса:
Допустим у графа $n$ вершин. В каком диапазоне может находится степень некоторой его вершины?

от 1 до (n-1)

 
 
 
 Re: Неориентированные графы
Сообщение04.11.2013, 22:53 
Почему 1, а не 0? О связности графа ничего не сказано, вершина может быть изолированной.

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

 
 
 
 Re: Неориентированные графы
Сообщение04.11.2013, 22:59 
germ9c в сообщении #784687 писал(а):
Показать , что в любом графе без петель и кратных ребер , содержащем не менее двух вершин, найдутся две вершины с одинаковыми степенями . (степень вершины графа определяется числом инцидентных этой вершине ребер

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

 
 
 
 Re: Неориентированные графы
Сообщение04.11.2013, 23:06 
Что-то не то. Вы не описали, как именно следует, и никак не использовали число возможных кратностей.

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

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

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

 
 
 
 Re: Неориентированные графы
Сообщение05.11.2013, 17:47 
Аватара пользователя

(Оффтоп)

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

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

 
 
 
 Re: Неориентированные графы
Сообщение05.11.2013, 18:22 

(Оффтоп)

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

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

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

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

 
 
 
 Re: Неориентированные графы
Сообщение05.11.2013, 18:58 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Неориентированные графы
Сообщение05.11.2013, 19:32 

(Оффтоп)

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

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

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


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