El gràfic consta de vèrtexs i arestes. Els vèrtexs estan connectats per arestes segons una propietat determinada: la relació d'incidència, que defineix el conjunt d'arcs. En aquest cas, es poden formar llaços i vèrtexs aïllats.
Manual d’instruccions
1
Permet donar un conjunt de vores d’un gràfic i una relació donada per la qual es pot dibuixar una vora d’un vèrtex a un altre. Com a exemple, el conjunt de vèrtexs {1, 2, 3, 4, 5, 6, 7, 8}, els dos vèrtexs x i y es troben en la relació x + y <8.
2
Construeix una matriu d’adacència de vèrtex. Per fer-ho, creeu una taula quadrada, el nombre de files i columnes de la taula coincideix amb el nombre de vèrtexs. Després poseu 1 a la intersecció de la fila i i de la columna j, si els vèrtexs i i j satisfan la proporció donada. Poseu 0 a la intersecció de la fila i i de la columna j, si la proporció dels elements corresponents no es compleix.
En el nostre exemple, la primera línia s'omple de la següent manera:
1 + 1 <8, de manera que a la intersecció de la 1a fila i la 1a columna hi ha 1
1 + 2 <8, de nou 1
1 + 3 <8, de nou 1
…
1 + 7 <8, desigualtat incorrecta, aquest element de taula serà 0
1 + 8 <8, de nou 0
3
Per esbrinar el nombre d'arcs, compteu el nombre d'unitats de la matriu d'adjacència, mentre no trinxeu les arestes.
En l'exemple, es va obtenir una matriu simètrica, per tant, primer es van calcular les unitats per sobre de la diagonal principal de la matriu (marcada en blau), i després les unitats de la diagonal principal (marcades en vermell). El nombre total de costelles és de 12.
4
Construeix una matriu d’incidents (arestes). Per fer-ho, dibuixa una taula, el nombre de files que hi ha és igual al nombre de vèrtexs del gràfic i el nombre de columnes és igual al nombre d'arcs. Poseu les unitats en les línies que estaran connectades per una vora. Les vores que porten de la part superior fins a ella s’anomenen bucles i s’afegeixen a l’extrem de la matriu. A les columnes corresponents als bucles, només hi ha una unitat, a diferència de les altres vores.
5
Ara dibuixa un gràfic. Organitzar els vèrtexs del paper de forma arbitrària i connectar-los amb vores mitjançant les taules construïdes. Els vèrtexs no connectats per les vores s'anomenen aïllats.
Pareu atenció
La figura mostra les costelles per obtenir més claredat. Normalment, el pes de la costella s’escriu sobre la costella.
