Подумалось, что самый сложный и интересный курс за время моего обучения в университете наверное заслуживает отдельной ветки. Думать - это хорошо и полезно, так что присоединяемся. Спрашивайте свои ответы, буду отвечать на них по мере компетентности. Пара простых задач для затравки: 1) Доказать, что в любом графе найдутся две вершины равной степени. 2) Доказать, что у двудольного регулярного графа доли равномощны. Пара задач, относительно решения которых я до сих пор нахожусь в глубоких непонятках: 3) Граф G 2-связен и для любых двух несмежных вершин u и v граф G-u-v несвязен. Доказать, что граф G является простым циклом. 4) Найти граф G - 2-рёберно-связный, для которого граф G^2 - негамильтонов. 5) Доказать, что граф эйлеров тогда и только тогда, когда любой его блок эйлеров. блок есть максимальная по включению 2-связная компонента, граф G^2 - граф с тем же множеством вершин, у которого две вершины соединены ребром тогда и только тогда, когда в графе G они соединены некоторой простой цепью длины не более двух.
>>6456 > 1) Доказать, что в любом графе найдутся две вершины равной степени. А если граф состоит из одной вершины? :3
> 1) Доказать, что в любом графе найдутся две вершины равной степени.
Есть ли какая-нибудь литература для дум-дум* рода людей (или хотя бы с очень подробными описаними и множеством повторений)? Я люблю графы, но очень, очень и очень туго соображаю.
Хорошая кафедра. Графы отдельным курсом в нашем техникуме(пока?) не преподавали, может, научусь здесь чему-нибудь. Какую литературу (желательно посвежее, развивающаяся область, как-никак) можете посоветовать по курсу?
>>6458 Упс, забыл условие. Само собой, для двух и более вершин.:) >>6459 Хорошая литература для дум-дум - мой конспект лекций, в скором времени собираюсь его оцифровать. А пока можно послушать: http://www.intuit.ru/department/ds/discretemath/11/ понятно, доступно и читать не надо. Появляющиеся неясности спрашивайте прямо тут. >>6462 Могу поделиться парой вещей, которые не шибко популярны в этих ваших интернетах, но у меня нашлись. Первая - краткий курс по основным определениям с большим уклоном в алгоритмику, что интересно программистам. Вторая - книжка моего преподавателя, с применением к ней метода прочтения "первые две страницы из каждой главы". а насчёт развивающейся области - у меня такое впечатление сложилось, что не особо. Теория упёрлась в несколько задач, которые уже достаточно долго не разрешены или не доказаны. Вот например ту же задачу о 4-х красках так толком и не доказали, но считают разрешенной, потому что перебором для больших-больших графов вроде раскрасить можно. Щас появился интерес к отдельным областям, в основном ради этих новомодных параллельных вычислений, но посоветовать толком ничего не могу. Да и как бы старой-престарой базы определений и теорем достаточно, чтобы на досуге поломать голову над какой-нибудь очередной задачкой. Собственно, удовольствие мне это приносит, а для этого я этим и занимаюсь)
>>6464 Спасибо! Обязательно погляжу. > задачу о 4-х красках так толком и не доказали, но считают разрешенной, потому что перебором для больших-больших графов вроде раскрасить можно. Разве? Доказали-то, насколько я понимаю, точно, однако при самом доказательстве необходимо было проверить туеву хучу вариантов, поэтому задействовали компьютер. А строго доказать корректность вычислений такой сложной системы(это же софт+компилятор+железо+сами физические принципы как минимум) очень сложно, если вообще возможно.
> задачу о 4-х красках так толком и не доказали, но считают разрешенной, потому что перебором для больших-больших графов вроде раскрасить можно.
>>6456 Алсо, в 4 задаче "простая цепь длины не более двух" - путь с длиной не более 2?
>>6466 Спасибо за инфу, буду знать >>6467 Термин "путь" обычно применяется в ориентированных графах, для неориентированных - "цепь". Собственно, "простая цепь" - сама себя в вершинах не пересекающая. Здесь: Несовпадающие вершины u и v в графе G-квадрат смежны тогда и только тогда, когда выполняется хотя бы одно из двух условий: 1) они смежны в графе G 2) в графе G существует ещё какая-нибудь вершина w, такая что "u смежна с w" и "v смежна с w".
You made my evening. А откуда задачи? :3 Первые три вроде бы решились быстро, а на четвёртой сел. Что-то мне сдаётся, что такого графа не существует вообще, однако доказать этот факт пока получается.
>>6472 Свежезаконченный (в четверг сдал) универовский спецкурс, и теория и практика. Третью можно узнать, как? :) Насчёт четвёртой задачи, да, есть большие сомнения относительно существования этого графа. Косвенные. Сарванов, мой преподаватель, является хорошим другом и частым гостем одного австрийского математика, доказавшего теорему о том, что если граф G 2-связен, то G-квадрат гамильтонов. Хотя, конечно, не все 2-реберно-связные графы 2-связные, но нехорошие подозрения закрадываются... Через полчасика вброшу ещё задач, чтоб запас был.
>>6456 > Третью можно узнать, как? :) Сперва скажи, привально ли я понял, что граф называется простым циклом, если он представляет из себя "ожерелье" из некоторого числа вершин. (таким образом степень всех вершин в таком графе равна 2) ? Что-то мне начинает казаться, что я решал не ту задачу.
> Третью можно узнать, как? :)
>>6472 Хотя не, вроде понял. Возведение графа в квадрат добавляет дополнительные пути, позволяющие обойти все вершины в произвольном графе по порядку и вернуться в начальную. Всё это, правда, совершенно неформально, но мне кажется не очень сложно составить формальный алгоритм построения гамальтонова цикла на таком графе.
>>6476 Ага, правильно. Типа треугольник, квадрат, пятиугольник, шестиугольник и т.д., никаких диагоналек нету.
>>6468 > Термин "путь" обычно применяется в ориентированных графах, для неориентированных - "цепь". Имхо гон. >>6456 Я, кажется, решил 3), причем там достаточно обычной связности. Только надо добавить, что граф должен быть неполон. Оп, вот тебе 2.5) в направлении на 3): доказать, что из любого связного графа с более чем одной вершиной можно выкинуть вершину, не нарушив связности.
> Термин "путь" обычно применяется в ориентированных графах, для неориентированных - "цепь".
>>6478 Хм, только что запорол 20-минутное доказательство случайно рефрешнув страницу, так что вот картинка к нему, а завтра, если будет ещё надо, приведу его самого. Хотя там, как написал >>6479-кун, всё вроде просто. > > Термин "путь" обычно применяется в ориентированных графах, для неориентированных - "цепь". > > > Имхо гон. Имхо проблема неустоявшихся терминов. Хотя в Кормене вроде тоже путём называют и путь, и цепь.
> > Термин "путь" обычно применяется в ориентированных графах, для неориентированных - "цепь".
>
> > Имхо гон.
>>6479 Если речь идет о выкидывании произвольной вершины, то это не так. Пикрилейтед - контрпример
Захотел попробовать сделать как сказал >>6444-кун, поэтому можно вас попросить гордых программ для построения графов?
>>6481 Да нет же. Существует такая вершина, что ее можно выкинуть.
>>6480 А у меня проще чем на этой картинке и эта "2.5" тут ни причем. При стягивании ребра единственное условие, которое может нарушиться - граф станет полным. Будем стягивать ребра до посинения, т.е. пока не получим полный граф. Что у нас было за ход до получения полного графа? Был полный подграф на всех вершинах, кроме двух, и две соединенные друг с другом вершины. Короче, если потыкать в эту конструкцию условием, то окажется, что это квадрат.
>>6485 ты про какую задачу вообще говоришь? В 3 нет квадрата. И что значит "стягивать рёбра"?
>>6482 > гордых программ Даже не знаю, что советовать... Emacs?
> гордых программ
>>6486 Блин, ну погугли "стягивание ребер", попадешь на словарик в рукипедии. Заодно поймешь, причем тут квадрат.
>>6488 > Заодно поймешь, причем тут квадрат. Почему тогда не треугльник или даже не точка с ребром в саму себя? А вообще, если ты хотел, чтобы тебя поняли, у тебя это сделать не получилось. Начиная с загадочного "потыкать" и кончая тем, почему при стягивании обязательно должен получиться полный граф.
> Заодно поймешь, причем тут квадрат.
>>6482 http://alenacpp.blogspot.com/2006/02/blog-post_14.html
>>6489 > А вообще, если ты хотел, чтобы тебя поняли, у тебя это сделать не получилось. Я хочу, чтобы меня понял ОП и я надеюсь, что он поймет.
> А вообще, если ты хотел, чтобы тебя поняли, у тебя это сделать не получилось.
>>6492 > При стягивании ребра единственное условие, которое может нарушиться - граф станет полным. Единственное ли? Граф волшебным образом из двусвязного может превратиться в односвязный, как на пикрилейтеде. И вообще, откровенно говоря, не понятно, в каком порядке мы рёбра стягиваем и что доказывает то, что это квадрат. ну стянули мы какую-то неведомую хуйню к квадрату. я могу кучу графов нарисовать, которые несколькими операциями стягивания рёбер можно привести к квадрату, и которые вовсе не будут изначально простыми циклами
> При стягивании ребра единственное условие, которое может нарушиться - граф станет полным.
>>6493 > из двусвязного может превратиться в односвязный А нам только связность-то и нужна на самом деле. Это я действительно должен был написать. Мы тянем по индукции связность, неполноту и условие об удалении двух вершин. > в каком порядке мы рёбра стягиваем По фигу. > ну стянули мы какую-то неведомую хуйню к квадрату Граф, из которого одним стягиванием ребра получается простой цикл и который удовлетворяет условию об удалении двух вершин, сам является простым циклом. Это понятно или объяснить?
> из двусвязного может превратиться в односвязный
> в каком порядке мы рёбра стягиваем
> ну стянули мы какую-то неведомую хуйню к квадрату
Вброшу пока говна в вентилятор 6) Привести пример графа, в котором любые 3 вершины принадлежат некоторому простому циклу, но существуют 4 вершины, которые не принадлежат никакому простому циклу. 7) Доказать, что любой граф является подграфом некоторого Δ(G)-регулярного. 8) Показать, что если G - связный, то существует маршрут, проходящий через все его рёбра, причем через каждое - не более двух раз. 9) Показать, что как минимум один из графов {G; его дополнение} связны. 10) Пусть x - вершина графа G и эта вершина инцидентна ребру e. Доказать, что если х не является разделяющей в графе G, то она не является разделяющей и в графе G-e. Сопутствующие определения: Простой цикл - простая цепь, у которой совпадают первая и последняя вершины. k-регулярный граф - граф, степень каждой вершины которого равна k. Δ(G) - максимальная степень вершины графа. Дополнение графа G - граф H, построенный на том же множестве вершин, в котором две вершины смежны тогда и только тогда, когда они не смежны в G. Если (u,v) - ребро, то говорят, что вершины u и v инцидентны этому ребру. Вершина разделяющая , или точка сочленения , если после её удаления в графе оказывается больше компонент связности, чем было до её удаления.
>>6496
>>6498 WE GOT A WINNER Лично я отвечал просто K3,4, то бишь полный двудольный граф с 3-мя вершинами в одной доле и 4-мя в другой
>>6496 Докажем по индукции. Для одной вершины очевидно. Пусть доказано для n, докажем для n+1. Если n+1-я соединена со всеми остальными, то граф связен. Если она не соединена со всеми остальными, то дополнение связно. Если ни то, ни другое, то посмотрим, что творится с подграфом на первых n вершинах. Если он связен, то и с новой вершиной связен, потому что она с чем-то соединена. Аналогично если дополнение связно.
>>6496 Пусть G - несвязен, покажем, что тогда его дополнение связно. Действительно, G - несвязен, значит представим в виде объединения k компонент связности Т1, Т2, ..., Тk, k>=2. Берём произвольную вершину v из компоненты Т1. В дополнении она смежна со всеми вершинами из компонент T2, ... Tk. Берём произвольную вершину u из компоненты T2, в дополнении она смежна с любой вершиной из компоненты T1, в том числе и с v. Выходит, что дполнение связно.
>>6496 Хммм... А не похуй ли, удалим мы из графа вершину или вершину и смежное ей ребро? Ведь когда мы удаляем вершину, мы удаляем и все рёбра её.
- wakaba 3.0.9 + futaba + futallaby -