2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Задачи по теории графов
Сообщение14.03.2008, 23:06 
1. Доказать, что из связного графа можно выбросить одну вершину, оставив его связным.
2. Доказать, что в планарном (плоском) графе найдётся вершина, из которой выходит не более 5 рёбер.
3. Доказать, что связный граф можно обойти, проходя по каждому ребру дважды.
4. Клетчатая плоскость раскрашена десятью красками так, что соседние (т. е. имеющие общую сторону) клетки покрашены в разные цвета, причём все десять красок использованы. Две краски называются соседними, если ими покрашены какие-то две соседние клетки. Каково минимально возможное число пар соседних красок?
5. В некоторой стране каждые два города соединены дорогой с односторонним движением. Докажите, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.
6. Рёбра дерева окрашены в два цвета. Если в какую-то вершину приходят рёбра только одного цвета, то их все можно перекрасить в другой цвет. Можно ли все дерево сделать одноцветным?

 
 
 
 
Сообщение14.03.2008, 23:11 
Аватара пользователя
Что-то чрезчур типовые задачи. Это не домашнее задание случаем?

 
 
 
 
Сообщение14.03.2008, 23:17 
maxal писал(а):
Что-то чрезчур типовые задачи. Это не домашнее задание случаем?

Нет, не домашнее. Домашних мне уже несколько лет не задают). Я не "профессиональный" математик, а скорее любитель, поэтому, возможно, слегка ошибся с уровнем задач, когда посчитал их олимпиадными. )

 
 
 
 
Сообщение14.03.2008, 23:17 
Аватара пользователя
для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

 
 
 
 
Сообщение14.03.2008, 23:34 
maxal писал(а):
для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

Если найти, то всё очевидно. Неочевидно, что в отсутствие вершин степени 1 всегда найдётся цикл (по крайней мере, для меня :oops: )

 
 
 
 
Сообщение15.03.2008, 00:23 
Аватара пользователя
popkorn писал(а):
maxal писал(а):
для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

Если найти, то всё очевидно. Неочевидно, что в отсутствие вершин степени 1 всегда найдётся цикл (по крайней мере, для меня :oops: )

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

 
 
 
 
Сообщение15.03.2008, 00:39 
maxal писал(а):
popkorn писал(а):
maxal писал(а):
для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

Если найти, то всё очевидно. Неочевидно, что в отсутствие вершин степени 1 всегда найдётся цикл (по крайней мере, для меня :oops: )

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

А, всё, теперь очевидно )
Спасибо )

 
 
 
 
Сообщение15.03.2008, 09:44 
Аватара пользователя
Теперь мне объясните. Цикл мы найдем, но что дальше? Легко построить пример графа, в котором существует такой цикл, из которого нельзя выкинуть ни одной вершины. Т.е. надо еще найти подходящий цикл.

 
 
 
 
Сообщение15.03.2008, 10:28 
Аватара пользователя
Если в цикле нет вершин степени 2, то его нужно "запаковать" в одну вершину и повторить поиск, и так до тех пор пока не будет найдена вершина степени 1, из нее распаковываем циклы и находим вершину для удаления.
А вообще, наверное, проще в другую рассуждать - индукцией по числу вершин в графе.

 
 
 
 
Сообщение15.03.2008, 17:36 
Истинность второго утверждение мне чисто интуитивно кажется сомнительной.

 
 
 
 
Сообщение15.03.2008, 18:29 
PAV писал(а):
Теперь мне объясните. Цикл мы найдем, но что дальше? Легко построить пример графа, в котором существует такой цикл, из которого нельзя выкинуть ни одной вершины.
Теперь мне объясните. Че-то я с ходу не придумал, как построить такой граф. Если с некоторой вершиной цикла соседствуют только ее соседи по циклу, то ее смело можно выкидывать.

 
 
 
 
Сообщение15.03.2008, 19:23 
Аватара пользователя
popkorn писал(а):
Истинность второго утверждение мне чисто интуитивно кажется сомнительной.

Второе утверждение легко следует из рассмотрения эйлеровой характеристики...

 
 
 
 
Сообщение15.03.2008, 19:58 
Аватара пользователя
AD писал(а):
Теперь мне объясните. Че-то я с ходу не придумал, как построить такой граф. Если с некоторой вершиной цикла соседствуют только ее соседи по циклу, то ее смело можно выкидывать.


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

 
 
 
 
Сообщение15.03.2008, 20:13 
maxal писал(а):
popkorn писал(а):
Истинность второго утверждение мне чисто интуитивно кажется сомнительной.

Второе утверждение легко следует из рассмотрения эйлеровой характеристики...

Я пытался как-то её применить, но не очень получилось что-то )
Нельзя ли ещё подсказку )

 
 
 
 
Сообщение15.03.2008, 20:23 
Аватара пользователя
popkorn
От противного - предположите, что из каждой вершины выходит как минимум 6 ребер, и получите отсюда противоречие с эйлеровой характеристикой.

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


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