Wykres składa się z wierzchołków i krawędzi. Wierzchołki są połączone krawędziami według pewnej właściwości - relacji padania, która definiuje zbiór krawędzi. W takim przypadku mogą tworzyć się pętle i izolowane wierzchołki.
Instrukcje
Krok 1
Niech dany będzie zbiór krawędzi grafu i podana zostanie relacja, wzdłuż której można narysować krawędź od jednego wierzchołka do drugiego. Na przykład zbiór wierzchołków {1, 2, 3, 4, 5, 6, 7, 8}, dwa wierzchołki x i y są w stosunku x + y <8.
Krok 2
Zbuduj macierz sąsiedztwa wierzchołków. Aby to zrobić, zbuduj kwadratową tabelę, liczba wierszy i kolumn w tabeli pokrywa się z liczbą wierzchołków. Następnie umieść 1 na przecięciu i-tego wiersza i j-tej kolumny, jeśli wierzchołki i oraz j spełniają podany stosunek. Umieść 0 na przecięciu i-tego wiersza i j-tej kolumny, jeśli stosunek odpowiednich elementów nie jest spełniony.
W naszym przykładzie pierwsza linia jest wypełniona w następujący sposób:
1 + 1 <8, więc jest 1 na przecięciu 1. rzędu i 1. kolumny
1 + 2 <8, znowu 1
1 + 3 <8, znowu 1
1 + 7 <8, nieprawidłowa nierówność, więc ten element tabeli będzie wynosił 0
1 + 8 <8, znowu 0
Krok 3
Aby poznać liczbę krawędzi, policz liczbę jedynek w macierzy sąsiedztwa bez duplikowania krawędzi.
W przykładzie uzyskano macierz symetryczną, więc policzyliśmy najpierw te nad główną przekątną macierzy (zaznaczone na niebiesko), a następnie te na głównej przekątnej (zaznaczone na czerwono). Całkowita liczba żeber to 12.
Krok 4
Zbuduj macierz incydentów (krawędzi). Aby to zrobić, narysuj tabelę, w której liczba wierszy jest równa liczbie wierzchołków wykresu, a liczba kolumn jest równa liczbie krawędzi. Umieść jednostki na tych liniach, które będą połączone krawędzią. Krawędzie prowadzące od wierzchołka do niego nazywane są pętlami i są dodawane na końcu macierzy. W kolumnach odpowiadających pętlom jest tylko jedna jednostka, w przeciwieństwie do reszty krawędzi.
Krok 5
Teraz narysuj wykres. Wierzchołki umieść na papierze w dowolny sposób i połącz je z krawędziami za pomocą skonstruowanych tabel. Wierzchołki, które nie są połączone krawędziami, nazywane są izolowanymi.
