gráfművelet
Természetesen arra törekszik, hogy a szerkezet vizsgált gráf segítségével grafikont kisebb méretű és egyszerűbb szerkezetű. Érdemes röviden utal a grafikonok, amely gyakran megtalálható. Mi már bevezették jelölésére teljes gráf Kr és Cr kiegészítések, egyszerű ciklus Cn és Pn egyszerű áramkör, valamint a teljes páros gráf Km, n.
Ez a rész a grafikonok G1 és G2 jelentése diszjunkt halmazok csúcsok V1 és V2 diszjunkt halmazok X1 és X2 élek.
unió G1ÈG2 jelentése egy grafikon, beütésszám több csúcsú, amely V = V1ÈV2. és több bordák X = X1ÈX2
Vegyület grófok lépett Zykov - kijelölt G1 + G2, G1 állÈG2 és minden összekötő élek V1 és V2. Különösen, a K m, n = Km + Kn- Ezek a műveletek az ábrán látható. ahol G1 = K2 = P2 és G2 = K1,2 = P3
Ha a G - csatlakoztatott gráf, akkor egy kijelölt nG gráf n komponenseket, amelyek mindegyike izomorf G. Minden grafikont felírható UniGi, ahol Gi jelentése eltér a Gj, i! = J. Például, egy szétkapcsolt grafikon látható az ábrán felírható 4K1 È ZK2 È 2K3 È K1,2
Számos műveleteket grafikonok G1 és G2, amelyek egy G gráf a csúcsok halmaza egyenlő a Descartes-szorzat Vl X V2. Ezek közül, a terméket (vagy a Descartes-szorzat), a készítmény (vagy Iexikografikus termék).
Annak meghatározására, termék G1xG2 fontolóra bármely két csúcsot u = (u1, u2) és v = (V1, V2) a V = V1 X V2. Csúcsok u és v nem szomszédos G1XG2 akkor és csak akkor, ha [u1 = v1 és u2 ADJ v2] vagy [u2 = v2 és u1 mn u1]. Artwork grafikonok G1 = P2 és G2 = P3 látható
G készítmény = G1 [G2] is rendelkezik V = Vi x V2, mint több csúcsok és vertex u = (u1, u2) szomszédos a V = (V1, V2), ha és csak akkor, ha [u1 asj v1] vagy [U1 = a v1 és u2 mn v2]. A grafikonok G1 és G2, az ábrán látható, a két készítmény G1 [G2] és G2 [G1], ami nyilvánvalóan nem izomorfak, ábrán látható
Ha G1 és G2 - jelentése (p1, Q1) - és (P2, Q2) -graphs rendre, lehetőség van, hogy megtalálják a csúcsok száma és az élek száma a kapott gráf (lásd a 2.2.) Az egyes fent meghatározott műveleteket.
csúcsok száma élek száma