ALG$5

Rozdział 10

Elementy algorytmiki grafów

Grafy są niczym innym jak strukturą danych i poświęcenie im osobnego rozdziału może wzbudzić pewne zdziwienie u Czytelnika. Zabieg ten wydaje się jednak konieczny z uwagi na szczególne znaczenie grafów w algorytmice. Nie jest przesadą stwierdzenie, iż bez tej struktury danych niemożliwe byłoby rozwiązanie wielu problemów algorytmicznych.

Graty posiadają dość złożoną podbudowę teoretyczną (w zasadzie można naw'et wyodrębnić osobny dział matematyki tylko im poświęcony), ale w naszej prezentacji postaramy się uniknąć zbytniego formalizowania.

Odrobiona teorii zostanie przedstawiona jedynie w celu ścisłego umiejscowienia omawianego problemu, ale z założenia będzie to niezbędne minimum.

Czytelnikom zainteresowanym głębiej teorią grafów można w zasadzie polecić dowolny podręcznik algorytmiki, gdyż ta struktura danych zajmuje poczesne miejsce w' literaturze przedmiotu. Interesujące podejście, będące mieszaniną matematyki i informatyki, prezentuje [Hel86], ale nie jestem jednak w stanie potwierdzić, czy tytuł ten jest już dostępny na rynku wydawniczym w formie książkowej, czy też pozostał na zawrze uproszczonym skryptem uczelnianym.

Celem tego rozdziału jest zaprezentowanie minimalnej wiedzy (temat jest bow iem ogromny) dotyczącej grafów i sposobów ich reprezentacji w programach. Poznamy niezbędne słow nictwo związane z tą strukturą danych, jak również przedstawimy kilka typowych algorytmów, które ich dotyczą.

Patrząc z perspektywy historycznej, grafy „narodziły się” w roku 1736 dzięki niemieckiemu matematykowi L. Eulerowi. Przy ich pomocy rozwiązał on problem, który stawiali sobie mieszkańcy Koenigsberg, a mianowicie jak przemierzyć wszystkie siedem mostów znajdujących się w tym mieście, tak aby nie przechodzić dwukrotnie przez ten sam.