| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Разбитие одного графа на несколько |
| Автор: Mayk 28.6.2005, 21:17 |
| Есть граф, который невозможно обойти так, чтобы пройти через каждое ребро ровно один раз. Нужно разбить этот граф на минимальное кол-во графов в каждом из которых это возможно. Иными словами из произвольного рисунка нужно сделать минимальное кол-во рисунков, которые можно нарисовать не отрывая карандаша от бумаги. У кого какие идеи как это можно сделать? |
| Автор: SoWa 29.6.2005, 03:38 |
| А это граф или орграф? Это имеет значение. |
| Автор: ~FoX~ 29.6.2005, 08:22 |
| SoWa Скорее всего имеется ввиду ориентированный граф. Mayk Если есть кусок/ки котрый нельзя пройти не проходя два раза по ребру его и делай отдельным графом и исключай из исходного. Проверяй оба графа на "проходимость"........Количество полученных графов будет равно количеству "непроходимых" кусков. |
| Автор: Mayk 29.6.2005, 10:30 |
| SoWa Граф не ориентированый. Хотя про ориентированный тоже было бы интересно послушать. Задача представляет теоретический интерес. ~FoX~ А не может случиться так, что в один кусок можно поместить два и более ребра, через которые нельзя было пройти в исходном графе? |
| Автор: ~FoX~ 29.6.2005, 16:36 | ||||
Что за граф который нельзя обойти?
Так вот и выдиляй "непроходимое" ребро и еще одно в отдельный граф. |
| Автор: esperant0 29.6.2005, 16:46 | ||||
Обычный не Эйлеровский граф. Возьмите хотя бы задачу о мостах в Кенисберге. |
| Автор: Mayk 29.6.2005, 16:52 | ||||
...пройдя через каждое ребро лишь раз. Например тетраэдр. Или (топологически равный ему) значок мерса(грубо говоря, буква Y вписанная в окружность). Это нельзя нарисовать не отрывая карандаш от бумаги.
Определить то, что одно ребро мешает можно достаточно просто. А как определить, что если подцепить еще пару ребёр, то исходному графу полегчает? |
| Автор: poor_yorik 1.7.2005, 11:16 |
| Шаг 1. Выделяешь все копоненты связности. Для каждой делаешь шаг 2. Ответы сумируешь. Шаг 2. А) Если все вершины графа имеют парную степень, то значит можно обойти по одному разу. Ответ - 1. То же и для графа с одной вершиной. Б) Если есть вершины нечетной степени, то ответ - (количество вершин нечетной степени/2). Задача из Всеукраинской олипиады по программированию этого года.  |
| Автор: Mayk 1.7.2005, 21:30 | ||||
Вообще-то, если нечетных вершин две, то тоже можно за раз обойти. Нужно начать с нечетной вершины. Пример: квадрат и треугольник, у которых одна сторона общая.
В моём случае граф с одной вершиной гарантированно имеет ноль ребер. Задача стукнула в голову после непродолжительного рисования линий в OpenGL'е(там линии можно рисовать так- координата 0 и координата 1 определяет первую линию, координата n-1 и координата n, где n >= 2 определяют последующую линию). |
| Автор: poor_yorik 2.7.2005, 21:41 |
| Mayk, как раз это и правильно. Мой алгоритм находит минимальное количество частей на которые нужно разбить даный граф, чтобы в каждом из полученых графов можно было обойти все ребра по одному разу. А если у графа две непарные вершины, то начиная с одной из них мы можем обойти все ребра по разу и закончить в другой вершине. Значить граф нужно разбить на один граф ( ), что аналогично тому, чтобы даный граф ни на что не разбивать.Алгоритм правильный, это я гарантирую.  |
| Автор: Guest 12.7.2005, 17:41 |
| poor_yorik Вроде работает, но на счет связности кусуов не очень очевидно получается  (при условии связности исходного графа) |