De grafiek bestaat uit hoekpunten en randen. De hoekpunten zijn verbonden door randen volgens een bepaalde eigenschap - de incidentierelatie, die de reeks randen definieert. In dit geval kunnen zich lussen en geïsoleerde hoekpunten vormen.
instructies:
Stap 1
Laat de reeks randen van de grafiek worden gegeven en de relatie waarlangs het mogelijk is om een rand van het ene hoekpunt naar het andere te tekenen. Als voorbeeld, de verzameling hoekpunten {1, 2, 3, 4, 5, 6, 7, 8}, twee hoekpunten x en y zijn in de verhouding x + y <8.
Stap 2
Bouw een vertex-nabijheidsmatrix. Bouw hiervoor een vierkante tabel, het aantal rijen en kolommen in de tabel valt samen met het aantal hoekpunten. Zet dan 1 op het snijpunt van de i-de rij en de j-de kolom als de hoekpunten i en j voldoen aan de gegeven verhouding. Zet 0 op het snijpunt van de i-de rij en de j-de kolom als niet aan de verhouding voor de corresponderende elementen wordt voldaan.
In ons voorbeeld is de eerste regel als volgt ingevuld:
1 + 1 <8, dus er staat 1 op het snijpunt van de 1e rij en 1e kolom
1 + 2 <8, opnieuw 1
1 + 3 <8, opnieuw 1
1 + 7 <8, onjuiste ongelijkheid, dus dit element van de tabel wordt 0
1 + 8 <8, opnieuw 0
Stap 3
Om het aantal randen te weten te komen, tel het aantal enen in de aangrenzende matrix zonder de randen te dupliceren.
In het voorbeeld werd een symmetrische matrix verkregen, dus we telden eerst die boven de hoofddiagonaal van de matrix (blauw gemarkeerd) en daarna die op de hoofddiagonaal (rood gemarkeerd). Het totaal aantal ribben is 12.
Stap 4
Bouw een matrix van incidenten (randen). Teken hiervoor een tabel, het aantal rijen erin is gelijk aan het aantal hoekpunten in de grafiek en het aantal kolommen is gelijk aan het aantal randen. Zet eenheden op die lijnen die door een rand worden verbonden. De randen die van het hoekpunt ernaartoe leiden, worden lussen genoemd en worden aan het einde van de matrix toegevoegd. In de kolommen die overeenkomen met de lussen, is er slechts één eenheid, in tegenstelling tot de rest van de randen.
Stap 5
Teken nu een grafiek. Plaats de hoekpunten op een willekeurige manier op het papier en verbind ze met randen met behulp van de geconstrueerde tabellen. Hoekpunten die niet door randen zijn verbonden, worden geïsoleerd genoemd.
