De grafiek bestaat uit hoekpunten en randen. De hoekpunten zijn verbonden door randen volgens een bepaalde eigenschap - de incidentierelatie, die de set randen definieert. In dit geval kunnen lussen en geïsoleerde hoekpunten ontstaan.
Gebruiksaanwijzing
1
Laat een set randen van een grafiek worden gegeven en een relatie waarmee men een rand van het ene hoekpunt naar het andere kan tekenen. Als voorbeeld, de set hoekpunten {1, 2, 3, 4, 5, 6, 7, 8}, de twee hoekpunten x en y hebben de verhouding x + y <8.
2
Bouw een vertex-aangrenzende matrix. Om dit te doen, bouw een vierkante tabel, het aantal rijen en kolommen in de tabel komt overeen met het aantal hoekpunten. Plaats 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. Plaats 0 op het snijpunt van de i-de rij en de j-de kolom, als niet wordt voldaan aan de verhouding voor de overeenkomstige elementen.
In ons voorbeeld is de eerste regel als volgt gevuld:
1 + 1 <8, dus op het snijpunt van de 1e rij en 1e kolom is 1
1 + 2 <8, opnieuw 1
1 + 3 <8, opnieuw 1
…
1 + 7 <8, onjuiste ongelijkheid, dan is dit tabelelement 0
1 + 8 <8, opnieuw 0
3
Om het aantal randen te achterhalen, telt u het aantal eenheden in de aangrenzende matrix, zonder de randen te scheuren.
In het voorbeeld werd een symmetrische matrix verkregen, daarom werden eerst de eenheden berekend boven de hoofddiagonaal van de matrix (blauw gemarkeerd) en vervolgens de eenheden op de hoofddiagonaal (rood gemarkeerd). Het totale aantal ribben is 12.
4
Bouw een matrix van incidenten (randen). Teken hiervoor een tabel, het aantal rijen daarin is gelijk aan het aantal hoekpunten van de grafiek en het aantal kolommen is gelijk aan het aantal randen. Zet de eenheden in de lijnen die door een rand worden verbonden. De randen die van boven naar beneden lopen, worden lussen genoemd en aan het einde van de matrix toegevoegd. In de kolommen die overeenkomen met de lussen is er slechts één eenheid, in tegenstelling tot de andere randen.
5
Teken nu een grafiek. Schik de hoekpunten willekeurig op papier en verbind ze met randen met behulp van de geconstrueerde tafels. Hoekpunten die niet door randen zijn verbonden, worden geïsoleerd genoemd.
Let goed op
De afbeelding toont de ribben voor de duidelijkheid. Meestal wordt het gewicht van de rib over de rib geschreven.
