Задачи по теории графов

[popkorn]

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

[maxal]

Что-то чрезчур типовые задачи. Это не домашнее задание случаем?

[popkorn]

maxal писал(а):

Что-то чрезчур типовые задачи. Это не домашнее задание случаем?

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

[maxal]

для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

[popkorn]

maxal писал(а):

для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

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

[maxal]

popkorn писал(а):

maxal писал(а):

для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

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

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

[popkorn]

maxal писал(а):

popkorn писал(а):

maxal писал(а):

для примера подсказка для первой: найдите в графе вершину степени 1 или цикл...

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

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

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

[PAV]

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

[maxal]

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

[popkorn]

Истинность второго утверждение мне чисто интуитивно кажется сомнительной.

[AD]

PAV писал(а):

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

Теперь мне объясните. Че-то я с ходу не придумал, как построить такой граф. Если с некоторой вершиной цикла соседствуют только ее соседи по циклу, то ее смело можно выкидывать.

[maxal]

popkorn писал(а):

Истинность второго утверждение мне чисто интуитивно кажется сомнительной.

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

[PAV]

AD писал(а):

Теперь мне объясните. Че-то я с ходу не придумал, как построить такой граф. Если с некоторой вершиной цикла соседствуют только ее соседи по циклу, то ее смело можно выкидывать.

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

[popkorn]

maxal писал(а):

popkorn писал(а):

Истинность второго утверждение мне чисто интуитивно кажется сомнительной.

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

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

[maxal]

popkorn
От противного - предположите, что из каждой вершины выходит как минимум 6 ребер, и получите отсюда противоречие с эйлеровой характеристикой.