10.4 Speciális gráfok

Azt a gráfot, amelynek nincsenek élei, üres gráfnak nevezzük.

Egy gráf teljes, ha bármely két csúcsa szomszédos. Az n csúcspontú teljes gráf jelölése:  Kn. A Kn teljes gráf éleinek száma:

Egy G gráf komplemens gráfján azt a gráfot értjük, amelyre V()= V(G) és csúcspárra akkor és csak akkor, ha , azaz élei teljes gráffá egészítik ki G éleit.

Könnyű belátni az alábbi egyszerű állításokat:

Állítás-10.1: Ha G = G(m,n), akkor egy olyan n-ed rendű gráf, amelynek mérete:

Állítás-10.2: A Kn teljes gráf komplemens gráfja az n-ed rendű üres gráf.

Egy G gráfot r-reguláris gráfnak nevezünk, ha deg v = r a G gráf minden v csúcsára. Ha G = G(m,n) teljes gráf, akkor a G gráf  (n-1)-reguláris.

3. ábra. 4 csúcspontú reguláris gráfok

4. ábra. A Petersen gráf.

A 4. ábrán egy 10 csúcspontú 3-reguláris gráfot mutatunk be. A Petersen gráf több érdekes tulajdonsággal rendelkezik, ami miatt gyakran szerepel példaként különböző gráf-tulajdonságok bemutatásakor.

Egy G gráfot k-részesnek mondunk, k  1, ha a V(G) csúcspontjainak halmaza úgy particionálható k részhalmazra (V1,V2,...,Vk), hogy  E(G) elemei Vi és Vj-beli csúcsokat kötnek össze, ahol ij, azaz az egy partíción belüli két csúcs egyike sem szomszédos egymással.

Ha k = 2, akkor a gráf  kétrészes. Egy teljes kétrészes gráfot, ahol |V1| = r és |V2| = s K(r,s)-el vagy Kr,s-el jelöljük . (A K1,s gráfot  csillagnak nevezzük). A következő ábrán egy olyan kétrészes - nem teljes - gráf két izomorf ábrázolását mutatjuk be, amelyre |V1| = 4 és |V2| = 3.

 

5. ábra. Egy kétrészes gráf izomorf előállításai.

Állítás-10.3: Ha G egy r-reguláris kétrészes gráf, r 1, akkor |V1| = |V2|.