Grafiku përbëhet nga kulme dhe buzë. Kulmet lidhen me skaje sipas një veti të caktuar - relacioni i incidencës, i cili përcakton bashkësinë e skajeve. Në këtë rast, mund të formohen sythe dhe kulme të izoluara.
Udhëzimet
Hapi 1
Le të jepet bashkësia e skajeve të grafikut dhe të jepet relacioni përgjatë të cilit është e mundur të vizatoni një buzë nga një kulm në tjetrin. Si shembull, bashkësia e kulmeve {1, 2, 3, 4, 5, 6, 7, 8}, dy kulme x dhe y janë në raport x + y <8.
Hapi 2
Ndërtoni një matricë të afërsisë së kulmit. Për ta bërë këtë, ndërtoni një tryezë katrore, numri i rreshtave dhe kolonave në tabelë përkon me numrin e kulmeve. Pastaj vendosni 1 në kryqëzimin e rreshtit të i-të dhe kolonës j-të nëse vertices i dhe j përmbushin raportin e dhënë. Vendosni 0 në kryqëzimin e rreshtit të i-rë dhe kolonës së j-të nëse raporti për elementët përkatës nuk plotësohet.
Në shembullin tonë, rreshti i parë plotësohet si më poshtë:
1 + 1 <8, kështu që ka 1 në kryqëzimin e rreshtit të parë dhe kolonës së 1-të
1 + 2 <8, përsëri 1
1 + 3 <8, përsëri 1
1 + 7 <8, pabarazi e pasaktë, kështu që ky element i tabelës do të jetë 0
1 + 8 <8, përsëri 0
Hapi 3
Për të gjetur numrin e skajeve, numëroni numrin e atyre në matricën e afërsisë pa kopjuar skajet.
Në shembull, është marrë një matricë simetrike, kështu që ne kemi numëruar së pari ato mbi diagonalin kryesor të matricës (të shënuara me blu), dhe pastaj ato në diagonën kryesore (të shënuara me të kuqe). Numri i përgjithshëm i brinjëve është 12.
Hapi 4
Ndërtoni një matricë incidentesh (skajesh). Për ta bërë këtë, vizatoni një tabelë, numri i rreshtave në të është i barabartë me numrin e kulmeve në grafik, dhe numri i kolonave është i barabartë me numrin e skajeve. Vendosni njësi në ato linja që do të lidhen me një buzë. Skajet që çojnë nga kulmi në të quhen sythe dhe shtohen në fund të matricës. Në kolonat që korrespondojnë me sythe, ekziston vetëm një njësi, në kontrast me pjesën tjetër të skajeve.
Hapi 5
Tani vizatoni një grafik. Vendosni kulmet në letër në çdo mënyrë dhe lidhni ato me skaje duke përdorur tabelat e ndërtuara. Vertices që nuk janë të lidhur me skajet quhen të izoluara.
