Il grafico è costituito da vertici e bordi. I vertici sono collegati da bordi secondo una certa proprietà - la relazione di incidenza, che definisce l'insieme dei bordi. In questo caso, possono formarsi loop e vertici isolati.
Istruzioni
Passo 1
Sia dato l'insieme degli archi del grafo e sia data la relazione lungo la quale è possibile tracciare un arco da un vertice all'altro. Ad esempio, l'insieme dei vertici {1, 2, 3, 4, 5, 6, 7, 8}, due vertici x e y sono nel rapporto x + y <8.
Passo 2
Costruisci una matrice di adiacenza dei vertici. Per fare ciò, costruisci una tabella quadrata, il numero di righe e colonne nella tabella coincide con il numero di vertici. Quindi metti 1 all'intersezione della i-esima riga e j-esima colonna se i vertici i e j soddisfano il rapporto dato. Metti 0 all'intersezione della i-esima riga e j-esima colonna se il rapporto per gli elementi corrispondenti non è soddisfatto.
Nel nostro esempio, la prima riga è compilata come segue:
1 + 1 <8, quindi c'è 1 all'intersezione della prima riga e della prima colonna
1 + 2 <8, ancora 1
1 + 3 <8, ancora 1
1 + 7 <8, disuguaglianza errata, quindi questo elemento della tabella sarà 0
1 + 8 <8, ancora 0
Passaggio 3
Per scoprire il numero di spigoli, contare il numero di quelli nella matrice di adiacenza senza duplicare i bordi.
Nell'esempio è stata ottenuta una matrice simmetrica, quindi abbiamo contato prima quelle sopra la diagonale principale della matrice (segnate in blu), e poi quelle sulla diagonale principale (marcate in rosso). Il numero totale di costole è 12.
Passaggio 4
Costruisci una matrice di incidenti (bordi). Per fare ciò, disegna una tabella, il numero di righe in essa è uguale al numero di vertici nel grafico e il numero di colonne è uguale al numero di bordi. Metti le unità su quelle linee che saranno collegate da un bordo. I bordi che portano dal vertice ad esso sono chiamati loop e vengono aggiunti alla fine della matrice. Nelle colonne corrispondenti ai loop, c'è solo un'unità, in contrasto con il resto dei bordi.
Passaggio 5
Ora disegna un grafico. Posiziona i vertici sulla carta in qualsiasi modo e collegali con i bordi usando le tabelle costruite. I vertici che non sono collegati da bordi sono chiamati isolati.
