Teorija grafova – razlika između verzija

Graf G'=(V',E') je podgraf grafa G=(V, E) ako je skup njegovih čvorova (V') podskup skupa čvorova grafa G (V), a skup njegovih grana (E') je podskup skupa grana vektora G (E). Ako je ovim grafovima skup čvorova jednak, onda se graf G' naziva razapinjujućim grafom, ili skeletom.

 

Ako je stepen svakog čvora isti, onda je graf regularan. Kompletan graf je prost graf, kod koga su svaka dva čvora spojena granom.

 

Dva grafa, G₁, i G₂ su izomorfna ako i samo ako postoji „[[1-1]]“ i „[[Surjekcija|na]]“ preslikavanje vrhova i grana, tako da se očuvava susednost svih vrhova, tj. da su veze između vrhova načinjene na analogan način. Izomorfni grafovi su od velikog značaja u elektronici, pri konstruisanju štampanih kola, gde grane grafa (strujni vodovi) ne smeju da se seku osim u čvorovima. Zato je bitno da se pronađe izomorfan graf željenom grafu, ali takav da mu se grane ne seku.