Implementacija modula za rad s teorijeom grafova u programskom jeziku Ruby

Teorija grafova, moje omiljeno područje diskretne matematike. Jednostavni graf predstavlja skup (engl. set) objekata povezanih bridovima (engl. edges). Prema teoriji skupova, skup mora sadržavati isključivo jedinstvene vrijednosti što znači da su objekti i rubovi jedinstveni (bez duplikata). Postoje i grafovi (Multigrafovi) koji to dopuštaju, ali izlaze iz opsega ovog članka. Objekti u grafu se još mogu zvati i vrhovi (engl. vertices).

Neki poznati problemi Teorija grafova rješava nekoliko poznatih problema, vrlo jednostavno:

Problem trgovačkog putnika – ako trgovački putnik mora proći 10 gradova u državi, kako da ih obiđe sve, ali da pri tome potroši najmanje goriva tj. prijeđe najmanji put

Najutjecajnija osoba u vašoj mreži – vaš Twitter proizvod prate tisuće ljudi. Tko je od njih najutjecajnija osoba u vašoj mreži i gdje bi, kada bi izgubili tu osobu, izgubili primjetan dio tržišta

Bojanje grafa – poznati problem osobe za koju se smatra da je začetnik teorije grafova, Leonhard Euler, jedan od najpoznatijih matematičara u povijesti. Može li se proći svih 7 mostova u gradu Konigsberg, tako da se svaki most pređe isključivo jednom i da se na kraju vratimo u početnu točku?

Idemo definirati jedan vrh u Ruby-u.

Klasa je jednostavna, predstavlja jedan vrh s nekim imenom i informaciju o stupnju. Stupanj vrha se definira kao broj incidentnih (ulaznih i izlaznih) bridova.

Brid ćemo definirati kao skup dva vrha:

Definirana je metoda vertices koja vraća vrhove brida te metoda koja uspoređuje dva brida.

Obzirom da se graf sastoji od skupa vrhova i skupa bridova, potrebno je implementirati skup:

Skup bridova malo komplicira stvar jer je skup po definiciji jednoznačan tj. ne smiju postojati dva ista brida, a dva brida su ista ako i samo ako pokazuju na iste vrhove. Takvu usporedbu radi metoda edge? koja poziva metodu == koju smo definirali unutar klase Edge. Klasa se također brine oko povećanja stupnja vrhova onog trenutka kada se skup doda u graf. Sada imamo dovoljno stvari za implementirati jedan graf:

Na vrhu klase se nalazi konstruktor koji, kao parametre, prima vrhove i skup bridova. Takav pristup implementacije grafa se zove implementacija grafa listom susjedstva. Sljedeće dvije metode vertex? i edge? se koriste kada želimo pitati graf sadrži li neki vrh ili rub.

Stupanj grafa se jednostavno može dobiti ako pomnožimo broj rubova s brojem 2. Dokaz je lema o rukovanju.

Metoda adjacent? govori jesu li dva vrha susjedna, a min_degree i max_degree vraća najveći i najmanji stupanj vrhova u grafu.

Pokretanje grafa Napravit ćemo puni graf tj. graf u kojem su svi vrhovi povezani sa svima. Broj bridova je n x (n – 1) / 2.

Programski kod je dostupan ovdje.