Wykres składa się z wierzchołków i krawędzi. Wierzchołki są połączone krawędziami zgodnie z pewną właściwością - relacją padania, która określa zbiór krawędzi. W takim przypadku mogą się tworzyć pętle i izolowane wierzchołki.
Instrukcja obsługi
1
Niech zostanie podany zestaw krawędzi wykresu i relacja, dzięki której można narysować krawędź z 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.
2)
Zbuduj macierz przylegania wierzchołków. Aby to zrobić, zbuduj kwadratową tabelę, liczba wierszy i kolumn w tabeli odpowiada liczbie wierzchołków. Następnie umieść 1 na przecięciu i-tego rzędu i j-tej kolumny, jeśli wierzchołki iij spełniają podany stosunek. Umieść 0 na przecięciu i-tego rzędu i j-tej kolumny, jeśli stosunek dla odpowiednich elementów nie jest spełniony.
W naszym przykładzie pierwszy wiersz jest wypełniony w następujący sposób:
1 + 1 <8, więc na przecięciu 1. rzędu i 1. kolumny znajduje się 1
1 + 2 <8, ponownie 1
1 + 3 <8, ponownie 1
…
1 + 7 <8, niepoprawna nierówność, wówczas ten element tabeli będzie wynosił 0
1 + 8 <8, ponownie 0
3)
Aby dowiedzieć się o liczbie krawędzi, policz liczbę jednostek w macierzy przylegania, nie przerywając krawędzi.
W przykładzie uzyskano macierz symetryczną, dlatego najpierw jednostki zostały obliczone powyżej głównej przekątnej matrycy (zaznaczone na niebiesko), a następnie jednostki na głównej przekątnej (zaznaczone na czerwono). Łączna liczba żeber wynosi 12.
4
Zbuduj macierz zdarzeń (krawędzie). Aby to zrobić, narysuj tabelę, liczba wierszy w niej jest równa liczbie wierzchołków wykresu, a liczba kolumn jest równa liczbie krawędzi. Umieść jednostki w liniach, które zostaną połączone krawędzią. Krawędzie prowadzące od góry do niego są nazywane pętlami i dodawane na końcu matrycy. W kolumnach odpowiadających pętlom znajduje się tylko jedna jednostka, w przeciwieństwie do innych krawędzi.
5
Teraz narysuj wykres. Ułóż wierzchołki na papierze dowolnie i połącz je z krawędziami za pomocą zbudowanych tabel. Wierzchołki niepołączone krawędziami nazywane są izolowanymi.
Zwróć uwagę
Na rysunku pokazano żebra dla przejrzystości. Zwykle ciężar żebra zapisuje się nad żebrem.
