Il grafico è costituito da vertici e bordi. I vertici sono collegati da bordi in base a una determinata proprietà: la relazione di incidenza, che definisce l'insieme di bordi. In questo caso, possono formarsi anelli e vertici isolati.
Manuale di istruzioni
1
Consentire una serie di spigoli di un grafico e una relazione in base alla quale si può tracciare un spigolo da un vertice all'altro. Ad esempio, l'insieme di vertici {1, 2, 3, 4, 5, 6, 7, 8}, i due vertici xey sono nel rapporto x + y <8.
2
Crea una matrice di adiacenza dei vertici. Per fare ciò, crea una tabella quadrata, il numero di righe e colonne nella tabella corrisponde al numero di vertici. Quindi metti 1 all'intersezione della riga i-esima e la colonna j-esima, se i vertici iej soddisfano il rapporto dato. Metti 0 all'intersezione della riga i-esima e la colonna j-esima, se il rapporto per gli elementi corrispondenti non è soddisfatto.
Nel nostro esempio, la prima riga è riempita come segue:
1 + 1 <8, quindi all'intersezione della 1a riga e 1a colonna è 1
1 + 2 <8, di nuovo 1
1 + 3 <8, di nuovo 1
…
1 + 7 <8, disuguaglianza errata, quindi questo elemento della tabella sarà 0
1 + 8 <8, di nuovo 0
3
Per scoprire il numero di spigoli, conta il numero di unità nella matrice di adiacenza, senza strappare i bordi.
Nell'esempio, è stata ottenuta una matrice simmetrica, quindi prima le unità sono state calcolate sopra la diagonale principale della matrice (segnata in blu), quindi le unità sulla diagonale principale (segnata in rosso). Il numero totale di costole è 12.
4
Costruisci una matrice di incidenti (bordi). Per fare ciò, disegna una tabella, il numero di righe in esso è uguale al numero di vertici del grafico e il numero di colonne è uguale al numero di spigoli. Metti le unità nelle linee che saranno collegate da un bordo. I bordi che conducono dall'alto verso l'alto sono chiamati loop e aggiunti all'estremità della matrice. Nelle colonne corrispondenti agli anelli, c'è solo un'unità, a differenza degli altri bordi.
5
Ora disegna un grafico. Disporre arbitrariamente i vertici su carta e collegarli ai bordi utilizzando le tabelle costruite. I vertici non collegati dai bordi vengono chiamati isolati.
Presta attenzione
La figura mostra le nervature per maggiore chiarezza. Di solito, il peso della nervatura è scritto sulla costola.
