11. Síkgráf, síktérkép

Question 1

Síkgráf

Answer 1

• Egy tetszőleges $G=(V,E)$ gráf síkba teríthető vagy síkbeli ha léteznek olyan $f:V→ \R^2$ és $g:E→ P(\R^2 )$ (f,g injektívek) $(|P| = 2^{|x|} )$ függvények amelyekre egyrészt $e={x, y}$ esetén $g(e)$ egy tetszőleges, az $f(x)$ és $f(y)$ pontokat összekötő ív/görbe, másrészt az éleknek megfelelő ívek csak a közös végpontjaikban metszik egymást. (síkbarajzolható gráf olyan gráf, melynek létezik a síkba való beágyazása, tehát lerajzolható úgy a síkon, hogy élei kizárólag a csúcspontokban találkoznak.) $K_5, K_{3,3}$ nem rajzolhatók síkba.(K=komplett/teljes gráf, minden csúcs minden csúccsal össze van kötve. Ezekhez ábrát is illik rajzolni.)

Question 2

Síktérkép

Answer 2

• Síkbeli térképnek a sík egészének vagy egy korlátos tartományának tetszőleges olyan partícióját értjük, amelyben a partíció osztályai szintén tartományok.

Question 3

Kuratowski tétele

Answer 3

• Egy tetszőleges G gráf pontosan akkor teríthető síkba, ha nem tartalmaz $K_5$ vagy $K_{3,3}$-al homeomorf részgráfot.

Question 4

Kuratowski tétele, pontdiszjunkt utakkal

Answer 4

• Egy $G=(V,E)$ gráf pontosan akkor tartalmaz egy adott $H=(W,F$) gráffal homeomorf részgráfot, ha léteznek olyan
  $f:W→V$
  és
  $g:F→P(E)$
  injektív függvények, amelyekgre $g(e)$ egy, az $f(x)$ és $f(y)$ csúcsokat összekötő egyszer út minden $e={x, y} ∈E$ él esetén, és a $g(e)$ $(e∈E)$ utak végpontjaik kivételével páronként pontdiszjunktak. (A homeomora a tartalmazást és a pontdiszjunkt utak reprezentációját jelenti)
• Tetszőleges G gráf éleinek, csúcsainak elhagyásával és másodfokú csúcsainak éllel helyettesítésével kapott H gráfot a G gráf minorjának nevezzük, és
  $H \preceq G$
  jellel jelöljük.
• Tétel: G síkbeli ⇔ mindkettő igaz:
  a) Nincs benne 5 csúcs $P_1, P_2, P_3, P_4, P_5 ∈V$ amelyek között lenne $P_i$-ből $P_j$ -be pont diszjunkt utak. ⇔ $K_5 ≺ G$ (nincs benne) (Pontdiszjunkt utak: olyan utak, melyeknek a kezdő és végpontjukon kívül nincsen közös pontjuk.)
  b) Nincs benne $A_1, A_2, A_3, B_1, B_2, B_3 ∈V$ amelyek között lennének bármely $A_i$-ből $B_j$ -be pontdiszjunkt utak ⇔ $K_{3,3} ≺ G$(nincs benne)
• Fáry tétele: Ha síkba teríthető egy G gráf, egyenes vonalakkal is síkba teríthető.(Ez inkább elméleti jelentőség, mivel nagy helyigény egyenes vonalakkal kiteríteni egy gráfot.)

Question 5

Euler I poliédertétele:

Answer 5

• Legyen G egy tetszőleges összefüggő, síkba rajzolható gráf. Ekkor $l+c-e=2$ ahol a c és e a gráf csúcsainak ill. éleinek száma, míg l a G gráf síkba terítése után keletkezett lapok száma. (A gráfon kívüli végtelen tartományt is 1 lapnak kell tekintenünk). Bizonyítás: Tudjuk, hogy összefüggő gráf tetszőleges, körben levő élét elhagyva a gráf összefüggő marad. Minden iyen él pontosan két lapot határol, így elhagyásakor a két lap egybefolyik, vagyis a lapok és élek száma 1-el csökken, a csúcsok száma nem változik. Ha ezt addig ismételjük, amíg körmentes nem lesz a gráfunk, akkor 1 síkrész marad, vagyis l-1-szer hagytunk el élt. A megmaradt gráfnak $e’=e-(l-1)$ élet lesz, és az összes c csúcs megmarad. Mivel a megmaradt gráf összefüggő fa lesz, így a csúcsai között a $c-1=e’$ összefüggés áll fent. Mindkét oldalhoz l-1-et adva a $c+l-2=e$ egyenlőséget kapjuk.

Question 6

Euler I poliédertétele következménye

Answer 6

• Tetszőleges egyszerű síkba rajzolható gráf esetén
  $e ≤ 3c − 6$
  minden lapot legalább 3 él határol, vagyis minden lap legalább háromszög, minden él két lapnál van gyelembe véve, így $e ≥ \frac32 l$.
• $K_5$ nem síkbeli, mert $e=10, c=5$, vajon $e ≤ 3c − 6$? Nem, mert $10 \nleq 3 · 5 − 6$.
• Tetszőleges egyszerű síkba rajzolható páros gráf esetén
  $e ≤ 2c − 4$
  minden lap legalább 4 szög, $e ≥ \frac 4 2$ .
• $K_{3,3}$ nem síkbeli, mert $e=9, c=6$, vajon $e ≤ 2c − 4$? Nem, mert $9 \nleq 2 · 6 − 4$.
• Tetszőleges egyszerű síkba rajzolható gráf esetén, ha g (girth) jelöli a gráf legrövidebb körének hosszát (derékbőségét) akkor
  $e ≤ \frac{g}{g − 2} · (c − 2)$
  (Ez alapján is beláthatjuk hogy $K_5$ és $K_{3,3}$ nem síkbeli, órán elhangzott, előbbinél $g=3, e= 10, c=6$, utóbbinál $g=4, e=9, c=6$) Ha G-ben van hurokél, akkor $g=1$.

Question 7

Fullerének

Answer 7

• A szén harmadik tiszta módusulata a “futballabda”($C_{60}$ fullerén molekula) molekula. Fullerén molekulában 12 db 5 szög van és akárhány 6-szög.

Question 8

Más felületre rajzolható gráfok:

Answer 8

• Ha az F felületnek van egy (véges) síkbeli tartománnyal homeomorf (azaz megegyező) része, mint pl a gömbnek, túrusznak, Möbius szalagnak, Klein-palacknak, akkor persze minden síkba rajzolt gráf az F felületre is rajzolható, hiszen gráfjaink végesek, és rajzunk mérete tetszőleges méretűre kicsinyíthető.
• Egy tetszőleges G gráf pontosan akkor rajzolható gömbre, ha síkba rajzolható.
• Minden síkra rajzolható gráf felrajzolható tóruszra(úszógumi) és Möbius-szalagra is, mivel ezek a felületek is tartalmaznak a sík és egy nyílt környezetével homeomorf részt, visszafele nem igaz, mivel $K_7, K_{3,3}$ rajzolható tóruszra