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
i ≠ j, azaz az egy partíción
belüli két csúcs egyike sem szomszédos egymással.
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|.