Как научиться решать задачи на графы?

[kappa937]

Здравствуйте. Есть необходимость научиться решать олимпиадные задачи на графы. В общем, поизучал основные вещи: что вообще есть граф, какими они бывают и всё в этом роде, но никак не могу перейти от теории к решениям. Проблема возникает после представления графа в памяти.
В общем-то, научился представлять граф матрицей инцидентности и матрицей смежности, однако не могу понять: как составлять алгоритмы используя эти матрицы?
К примеру, мне нужно узнать самый длинный хвост графа. На этом рисунке он равен трем:



Думаю, понятно, о чем я.

С помощью матрицы смежности я нашел вершины 6, 9 и 5. (Пробегаюсь по строкам матрицы и считаю кол-во единиц, получается кол-во ребер для i-той вершины) То есть те, от которых надо пробежаться до основания "хвоста" (вершина 4).
Но как, собственно, "пробежаться", используя эту матрицу?

И, в общем, какие задачи чаще всего даются по графам и самое главное: как их научиться решать, представляя в памяти как двумерные массивы (или, может быть, есть более удобные способы) ?

Заранее спасибо.

[BDA]

Для тренировки можно, например, порешать тут - http://informatics.mccme.ru/course/view.php?id=6.

По задаче. Предполагаю. Нашли по матрице смежности все строки с одной единичкой. Для каждой найденной вершины Z: переходим в строку для вершины D, помеченной единичкой, и проверяем, есть ли там две единички. Если да (вершина D лежит в хвосте), то увеличиваем счетчик и переходим к следующей вершине K, если нету (или конец хвоста, или вершина D с несколькими хвостами), то увеличиваем счетчик и заканчиваем поиск для вершины Z.

[kappa937]

BDA, спасибо!

[kappa937]

В общем, возникла проблема.
BDA, видимо, я неверно вас понял.
Делаю так:
Нахожу основание для хвоста (на этом примере это вершина 4), в цикле прохожусь от одной из вершин (6, 9 и 5) до 4, проверяю все строки и смотрю, есть ли там 2 единицы.
То есть для 6 проверяется две строки, для 5 - одна, а для 9 - 5.
Этот способ срабатывает и находит на этом примере 3. Но что если сделать, например, так:

Тогда от вершины 10 до основания хвоста 4 пройдут целые 6 строк, и количество тех, в которых по 2 единицы - не совпадут с длиной этого хвоста.
Как быть?

[BDA]

Да, пожалуй, неверно.
Матрица смежности для последней картинки:

  1 2 3 4 5 6 7 8 9 10
 1  * * *
 2*   * *
 3* *   *
 4* * *   * * *
 5      *           *
 6      *
 7      *       *
 8            *   *
 9              *
10        *

6 9 10 вершины - концы хвостов (один переход в таблице).
Для вершины 10:
В матрице указан переход к 5 вершине - +1 к счетчику, переход к 5
Для 5 вершины в матрице 2 перехода (к 4 и к 10) - +1 к счетчику, переход к 4
Для 4 вершины в матрице 6 переходов = узел - возврат из рекурсии (цикла)
результат для 10 вершины = 2

Аналогично для 6 и 9.

[kappa937]

Наконец всё получилось, огромное спасибо! )