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

У кого какие идеи как это можно сделать?

Это сообщение отредактировал(а) Mayk - 29.6.2005, 10:30

А это граф или орграф? Это имеет значение.

SoWa
Скорее всего имеется ввиду ориентированный граф.


Mayk
Если есть кусок/ки котрый нельзя пройти не проходя два раза по ребру его и делай отдельным графом и исключай из исходного. Проверяй оба графа на "проходимость"........Количество полученных графов будет равно количеству "непроходимых" кусков.

SoWa
Граф не ориентированый. Хотя про ориентированный тоже было бы интересно послушать. Задача представляет теоретический интерес.

~FoX~
А не может случиться так, что в один кусок можно поместить два и более ребра, через которые нельзя было пройти в исходном графе?

Цитата(Mayk @ 29.6.2005, 11:30)

Граф не ориентированый. Хотя про ориентированный тоже было бы интересно послушать. Задача представляет теоретический интерес.

Что за граф который нельзя обойти?

Цитата(Mayk @ 29.6.2005, 11:30)

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

Так вот и выдиляй "непроходимое" ребро и еще одно в отдельный граф.

Цитата

Цитата(Mayk @ 29.6.2005, 11:30) Граф не ориентированый. Хотя про ориентированный тоже было бы интересно послушать. Задача представляет теоретический интерес. Что за граф который нельзя обойти?

Обычный не Эйлеровский граф. Возьмите хотя бы задачу о мостах в Кенисберге.

Цитата

Что за граф который нельзя обойти?

...пройдя через каждое ребро лишь раз. Например тетраэдр. Или (топологически равный ему) значок мерса(грубо говоря, буква Y вписанная в окружность). Это нельзя нарисовать не отрывая карандаш от бумаги.

Цитата

Так вот и выдиляй "непроходимое" ребро и еще одно в отдельный граф.

Определить то, что одно ребро мешает можно достаточно просто. А как определить, что если подцепить еще пару ребёр, то исходному графу полегчает?

Шаг 1. Выделяешь все копоненты связности. Для каждой делаешь шаг 2. Ответы сумируешь.
Шаг 2. А) Если все вершины графа имеют парную степень, то значит можно обойти по одному разу. Ответ - 1. То же и для графа с одной вершиной.
Б) Если есть вершины нечетной степени, то ответ - (количество вершин нечетной степени/2).

Задача из Всеукраинской олипиады по программированию этого года.

Цитата(poor_yorik @ 1.7.2005, 12:16)

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

Вообще-то, если нечетных вершин две, то тоже можно за раз обойти. Нужно начать с нечетной вершины. Пример: квадрат и треугольник, у которых одна сторона общая.

Цитата(poor_yorik @ 1.7.2005, 12:16)

То же и для графа с одной вершиной

В моём случае граф с одной вершиной гарантированно имеет ноль ребер. Задача стукнула в голову после непродолжительного рисования линий в OpenGL'е(там линии можно рисовать так- координата 0 и координата 1 определяет первую линию, координата n-1 и координата n, где n >= 2 определяют последующую линию).

Это сообщение отредактировал(а) Mayk - 1.7.2005, 21:34

Mayk, как раз это и правильно. Мой алгоритм находит минимальное количество частей на которые нужно разбить даный граф, чтобы в каждом из полученых графов можно было обойти все ребра по одному разу.
А если у графа две непарные вершины, то начиная с одной из них мы можем обойти все ребра по разу и закончить в другой вершине. Значить граф нужно разбить на один граф ( ), что аналогично тому, чтобы даный граф ни на что не разбивать.
Алгоритм правильный, это я гарантирую.

poor_yorik
Вроде работает, но на счет связности кусуов не очень очевидно получается
(при условии связности исходного графа)