11. gyakorlat

Gráfok II

Gráf bejárás

• Séta: nincs feltétel \(\big(\varphi (e_i) = \{v_{i-1}, v_i\}\big)\)
• Vonal: séta, amelyben nincs él ismétlődés
• Út: vonal, amelyben nincs csúcs ismétlődés
• Kör: vonal, amely ugyanoda ér vissza (\(v_0 = v_n\))

Összefüggő gráf: bármely két csúcsa között vezet séta

További fogalmak

Izomorfia

Két gráf izomorf, ha a két gráf csúcsai kozott van olyan leképezés, ami az élek illeszkedését megtartja

Például: Ez a két gráf izomorf egymással

Típusfeladat: Lehet-e ezekből a fokszámokból gráfot alkotni?

5, 5, 5, 4, 4, 2

Fokszámok összege: \(5+5+5+4+4+2=25\)

Fokszámog összege páratlan, tehát nincs ilyen gráf.

6, 3, 3, 2, 2, 2, 0

\(7\) csúcsú gráfban a maximális fokszám \(6\). Ez azt jelenti, hogy az a csúcs minden csúccsal össze van kötve, tehát nincs olyan csúcs, ami nincs semmihez kötve. Viszont, van egy olyan csúcsunk, aminek a fokszáma 0. Ez egy ellentmondás, tehát nem létezik ilyen gráf.

5, 5, 5, 2, 2, 2, 1

A gráf felosztható két részgráfra, melyeknek fokszámai:

• 5, 5, 5
• 2, 2, 2, 1

Ha az első részgráfból kijövő kapcsolatokat minimalizálni akarjuk, akkor azt mondjuk, hogy az 5, 5, 5 részgráf teljes.

Ha az első részgráfból kijövő kapcsolatokat maximalizálni akarjuk, akkor azt mondjuk, hogy a 2, 2, 2, 1 részgráf minden csúcsa izolált.

Így, lesz két kapcsolat, amit a felső részgráfból nem tudunk semmihez se kapcsolni. Tehát, ez a gráf sem lehetséges.

Összefüggőség

Egy gráf BIZTOSAN összefüggő, ha:

• Csúcsainak száma \(|V|=2n+1\)
• Minden csúcs fokszáma \(\geq n\)
  • \(\forall v \in V: d(v)\geq n\)