Теория графов

[RawonaM]

Что-то тут было, но стерлось.

[RawonaM]

А теперь теоретический вопрос о планарных графах: можно ли сказать, что непростой граф (т.е. содержащий либо петли либо двойные ребра) планарный iff если сделать из него простой путем убирания всех петлей и двойных ребер — планарный?

П.С. В туториале тема мало затрагивается, связи с предыдущим сообщением нет.

[Квас]

А теперь теоретический вопрос о планарных графах: можно ли сказать, что непростой граф (т.е. содержащий либо петли либо двойные ребра) планарный iff если сделать из него простой путем убирания всех петлей и двойных ребер — планарный?

Очевидно, да. Если простой планарный граф уложить на плоскость, добавить крохотные петельки и ненамного раздвинуть, разодрав их, рёбра, то пересечений рёбер не будет.

Речь, естественно, о конечных графах.

[RawonaM]

Если простой планарный граф уложить на плоскость, добавить крохотные петельки и ненамного раздвинуть, разодрав их, рёбра, то пересечений рёбер не будет.

Результат этой вашей жестокой операции можно описать как дополняющий к дополняющему этого графа?

Собственно, мне это тоже вроде очевидно, но ведь нужно доказать перед использованием, наверное.

[Квас]

Если простой планарный граф уложить на плоскость, добавить крохотные петельки и ненамного раздвинуть, разодрав их, рёбра, то пересечений рёбер не будет.

Результат этой вашей жестокой операции можно описать как дополняющий к дополняющему этого графа?

Дополняющий к дополняющему определён однозначно, а петелек можно добавлять разное число.

Собственно, мне это тоже вроде очевидно, но ведь нужно доказать.

Это самое утверждение о планарности? Топология, однако. А каким инструментарием мы владеем? Надо теорему Понтрягина вспоминать.

[RawonaM]

Дополняющий к дополняющему определён однозначно, а петелек можно добавлять разное число.

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

[RawonaM]

Собственно, мне это тоже вроде очевидно, но ведь нужно доказать.

Это самое утверждение о планарности? Топология, однако. А каким инструментарием мы владеем? Надо теорему Понтрягина вспоминать.

По-моему весь инструментарий в теории графов — болтология. По крайней мере все доказательства кажутся такими, чисто языком поболтать.

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

[RawonaM]

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

У меня такой вопрос:
Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.
Достаточно легко доказывается обычными рассуждениями в духе теории графов.
2) Какое утверждение в книге, доказывает 1).

Вот тут не врубаюсь. В книге утверждений — по пальцам пересчитать, но ни одно из них имхо не доказывает.

Утверждения есть такие (самые вообще не втемные отбрасываю):
1) х(Kn)=n
2) x(G)=2 iff G двухсторонний граф с хотя бы одним ребром
3) x(G)<=d(G)+1          (d(G) — максимальная степень вершины из G)
4) x(G)<=d(G) кроме двух частных случаев.
5) d-вырожденный граф можно покрасить d+1 цветами
6) если G можно покрасить k цветами, то в G есть независимое подмножество размером .

Айдии?

[Квас]

Voulez-vous bien expliquer ces notations ?

[RawonaM]

Voulez-vous bien expliquer ces notations ?

Pardon
x(G)=  (ленюсь переключаться ), т.е. хроматический индекс, т.е. минимум цветов, которыми можно покрасить.
V(G)=количество вершин.
K_n= полный граф к количеством вершин n.
Какие еще не ясны?

[Квас]

Покрасили граф G, x(G), k красками.

А это что так много через запятую? x(G) = k?

[RawonaM]

Покрасили граф G, x(G), k красками.

А это что так много через запятую? x(G) = k?

Да, именно так. Че-то я поспешил

[Квас]

Айдии?

Да что-то не очень ясно.

1) х(Kn)=n
2) x(G)=2 iff G двухсторонний граф с хотя бы одним ребром
3) x(G)<=d(G)+1          (d(G) — максимальная степень вершины из G)
4) x(G)<=d(G) кроме двух частных случаев.
5) d-вырожденный граф можно покрасить d+1 цветами
6) если G можно покрасить k цветами, то в G есть независимое подмножество размером .

1) и 2) не подходят, потому что относятся к специальным графам. Односторонних оценок, даваемых 3) и 4), насколько понимаю, ни для чего не хватит. 5) ⇔ 3), насколько понимаю. 6) —

Думаю...

[RawonaM]

У меня такой вопрос:
Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.

Третий пункт там такой: 3) Покажите, что в G есть по меньшей мере k вершин со степенью k-1.

Я почуял неладное, и вот нашел контрпример: круг на четырех вершинах. x(G)=2, но нет в нем 2 вершины со степенью 1. Верно говорю? Написал на форум курса.

[Квас]

Я почуял неладное, и вот нашел контрпример: круг на четырех вершинах. x(G)=2, но нет в нем 2 вершины со степенью 1. Верно говорю?

Ну конечно. И вообще противоречит свойству 2).

[RawonaM]

Я почуял неладное, и вот нашел контрпример: круг на четырех вершинах. x(G)=2, но нет в нем 2 вершины со степенью 1. Верно говорю?

Ну конечно. И вообще противоречит свойству 2).

Почему противоречит?

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

[Квас]

Почему противоречит?

Можно привести сколько угодно примеров двудольных графов, у которых нет вершин степени 1.

[RawonaM]

Ошибку признали, сказали разошлют фикс по всем инстанциям.

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

Думаю, что из:

Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.

следует:

3) x(G)<=d(G)+1          (d(G) — максимальная степень вершины из G)

[Квас]

Думаю, что из:

Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.

следует:

3) x(G)<=d(G)+1          (d(G) — максимальная степень вершины из G)

Согласен. Вроде бы и 5) так же легко выводится.

[RawonaM]

Согласен. Вроде бы и 5) так же легко выводится.

Может быть. Но утверждение 2 сильнее вроде.

[RawonaM]

Дан простой граф G с вершинами V, правильно раскрашенными в цвета из множества А.
G' - дополняющий к G, правильно раскрашен цветами из B.

Для каждого v из V, подберем пару (a,b), так что а цвет v в G, а В цвет v в G'. Доказать, что нет двух вершин, для которых выходит та же пара (т.е. отображение инъективно).

Что скажете? У меня ничего не вышло

[RawonaM]

Из моего сегодняшнего экзамена:

Даны два дерева на вершинах V G₁=(V,E₁), G₁=(V,E₁).

Для каждой вершины v определим d1(v) - степень вершины на первом дереве, d2(v) степень вершины на втором дереве.

Доказать, что существует такой v, для которого d1(v)+d2(v)≤3.

[RawonaM]

Получается так: если предположить, что нет такой вершины, то сумма степеней всех вершин обоих графов >=4n (n количество вершин).

С другой стороны сумма степеней всех вершин дерева равна 2n-2, значит двух деревьев 4n-4.

Следовательно есть хоть одна такая вершина. Эх, такую фигню спорол.
А я просто написал >=3n и у меня вышла фигня.

[RawonaM]

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

Смотрю (wiki/en) Strong_orientation

In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge that makes it into a strongly connected graph. Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

Смотрю (wiki/en) K-edge-connected_graph

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Let G = (E,V) be an arbitrary graph. If G' = (E \ X,V) is connected for all X ⊆ E where |X| < k, then G is k-edge-connected. Trivially, a graph that is k-edge-connected is also (k−1)-edge-connected.

Смотрю в первую цитату снова: 2-edge-connected graph = is connected and has no bridge.

Вроде логично. Берем граф из трех вершин соединенных в треугольник, ставим стрелки по кругу. Получился сильно ориентированный граф? Вроде как да. Но ведь он 1-edge-connected!

Чего я недопонял?

[RawonaM]

А нет, подождите, он is connected and has no bridge. Значит таки 2-edge-connected?
Не понял я этого термина пока что.