Die grafiek bestaan uit hoekpunte en rande. Die hoekpunte word deur rande verbind volgens 'n sekere eienskap - die invalsverhouding, wat die stel rande definieer. In hierdie geval kan lusse en geïsoleerde hoekpunte vorm.
Instruksies
Stap 1
Laat die stel rande van die grafiek gegee word en die verband word gegee waarlangs dit moontlik is om 'n rand van een hoekpunt na 'n ander te trek. As voorbeeld is die stel hoekpunte {1, 2, 3, 4, 5, 6, 7, 8}, twee hoekpunte x en y in die verhouding x + y <8.
Stap 2
Bou 'n hoekpunt-aangrensingsmatriks. Om dit te doen, bou 'n vierkantige tabel, die aantal rye en kolomme in die tabel val saam met die aantal hoekpunte. Sit dan 1 op die kruising van die i-de ry en j-de kolom as die hoekpunte i en j aan die gegewe verhouding voldoen. Sit 0 op die kruising van die i-de ry en j-de kolom as die verhouding vir die ooreenstemmende elemente nie bereik word nie.
In ons voorbeeld word die eerste reël soos volg ingevul:
1 + 1 <8, dus is daar 1 op die kruising van die 1ste ry en 1ste kolom
1 + 2 <8, weer 1
1 + 3 <8, weer 1
1 + 7 <8, verkeerde ongelykheid, dus sal hierdie element van die tabel 0 wees
1 + 8 <8, weer 0
Stap 3
Om die aantal rande vas te stel, tel die aantal een in die aangrensende matriks sonder om die rande te dupliseer.
In die voorbeeld is 'n simmetriese matriks verkry, dus het ons eers die tellings bokant die hoofdiagonaal van die matriks (in blou gemerk) getel, en dan die op die hoofdiagonaal (gemerk in rooi). Die totale aantal ribbes is 12.
Stap 4
Bou 'n matriks van insidente (rande). Om dit te doen, teken 'n tabel, die aantal rye daarin is gelyk aan die aantal hoekpunte in die grafiek en die aantal kolomme is gelyk aan die aantal rande. Sit eenhede op die lyne wat deur 'n rand verbind word. Die rande wat vanaf die hoekpunt lei, word lusse genoem en word aan die einde van die matriks gevoeg. In die kolomme wat ooreenstem met die lusse, is daar net een eenheid, in teenstelling met die res van die rande.
Stap 5
Teken nou 'n grafiek. Plaas die hoekpunte op enige manier op die papier en verbind dit met die rande met behulp van die saamgestelde tafels. Hoekpunte wat nie deur rande verbind word nie, word geïsoleer genoem.
