Două grafice care diferă numai în numerotarea nodurilor și marginile se numesc izomorfe.
Acestea pot diferi o reprezentare grafică și matricea de adiacenta și incidență. Pentru a se asigura că cele două grafice - acesta este unul și același grafic, este necesar și suficient pentru a stabili una la o corespondență între ele.
Cerințe preliminare la două grafice sunt izomorfe:
1 au același număr de noduri și muchii
2. Nodurile grafice au același grad.
Dar punerea în aplicare a acestor proprietăți nu este o condiție suficientă pentru graficul izomorfismul.
Exemplu: Construcția grafic izomorfă graficul din exemplul anterior.
Cale și ciclu în grafic
O cale într-un grafic este o secvență de muchii care duce de la vârf la vârf.
Un ciclu este o cale, care are nodurile finale și inițiale coincid. Ciclul este simplu în cazul în care trece printr-un singur nod o dată.
ciclu lung este numărul de muchii din ea.
Dacă contorizați toate simple cicluri de lungime chiar, atunci graficul nu are nici un ciclu de lungime impar.
Graficul Connected este un simplu ciclu dacă și numai dacă toate nodurile sale au gradul 2.
La scoaterea din grafic o margine se poate obține atât grafic conectat și deconectat.
Edge AB este numit un pod. dacă este scos nodurile A și B sunt disjuncte.
În cazul în care orice margine este un pod
1. edge AB este un pod, dacă AB este singura cale care leagă nodul A la B.
2. AB este un pod care margine AB nu este în nici un ciclu.
3. AB. un pod în cazul în care există două vârfuri C1 și C2, astfel încât traseul trece prin AB lor de conectare.