Grafen består af hjørner og kanter. Højdepunkterne er forbundet med kanter i henhold til en bestemt egenskab - forekomstforholdet, der definerer kantsættet. I dette tilfælde kan der dannes løkker og isolerede hjørner.
Brugsanvisning
1
Lad et sæt kanter på en graf gives, og der gives en relation, hvormed man kan tegne en kant fra et toppunkt til et andet. Som et eksempel er sættet med vertikater {1, 2, 3, 4, 5, 6, 7, 8}, de to vertices x og y i forholdet x + y <8.
2
Byg en matrix til adskillelse af toppunktet. For at gøre dette skal du opbygge en firkantet tabel, antallet af rækker og kolonner i tabellen svarer til antallet af vertikater. Sæt derefter 1 i skæringspunktet mellem den i-th række og den j-th kolonne, hvis vertikale i og j opfylder det givne forhold. Sæt 0 i skæringspunktet mellem den i-th række og den j-th kolonne, hvis forholdet for de tilsvarende elementer ikke er opfyldt.
I vores eksempel udfyldes den første linje som følger:
1 + 1 <8, så i skæringspunktet mellem 1. række og 1. kolonne er 1
1 + 2 <8, igen 1
1 + 3 <8, igen 1
…
1 + 7 <8, forkert ulighed, så er dette tabelelement 0
1 + 8 <8, igen 0
3
For at finde ud af antallet af kanter skal du tælle antallet af enheder i tilstødningsmatrixen, mens du ikke ripper kanterne.
I eksemplet opnåedes en symmetrisk matrix, derfor blev enhederne først beregnet over matrixens hoveddiagonal (markeret med blåt) og derefter enhederne på hoveddiagonalen (markeret med rødt). Det samlede antal ribben er 12.
4
Lav en matrix af hændelser (kanter). For at gøre dette tegner du en tabel, antallet af rækker deri er lig med antallet af vertikater på grafen, og antallet af kolonner er lig med antallet af kanter. Sæt enhederne i de linjer, der vil blive forbundet med en kant. Kanterne, der fører fra toppen til det, kaldes løkker og tilføjes til slutningen af matrixen. I de søjler, der svarer til sløjferne, er der kun en enhed i modsætning til de andre kanter.
5
Tegn nu en graf. Arranger vertikaterne på papir vilkårligt og forbind dem med kanter ved hjælp af de konstruerede tabeller. Vertikater, der ikke er forbundet med kanter, kaldes isoleret.
Vær opmærksom
Figuren viser ribbenene for klarhed. Normalt er vægten af ribben skrevet over ribben.
