Gráfok - felújítás előtt álló vázlat

Fogalom Definíció
Gráf Csúcsok és élek olyan rendszere, melyben minden él két, nem feltétlen különböző csúcsot köt össze.
Síkgráf Olyan gráf, mely izomorf valamelyik síkra rajzolt gráffal.
Síkra rajzolt  gráf Olyan gráf, melynek csúcsai a sík pontjai, élei pedig egymást csúcsban metsző különböző pontban nem metsző folytonos görbék.
Két gráf izomorf… Két gráf izomorf, ha létesíthető csúcsaik és éleik között kölcsönösen egyértelmű illeszkedés tartó leképezés.
Egyszerű gráf Azokat a gráfokat, melyekben nincs sem többszörös él, sem hurokél, egyszerű gráfoknak nevezzük.
Teljes gráf Olyan egyszerű gráf, melyben minden lehetséges él szerepel.
Üres gráf A teljes gráf komplementere.
Fokszám A gráf egy pontjába összefutó élek számát a pont fokszámának (röviden fokának) nevezzük.
Séta Egymáshoz kapcsolódó csúcsok és élek sorozata.
Lap Azok a sokszögek, amelyek a síkgráf élei által létrejönnek Euler-tétellel kompatibilis síkgráfokra.
Összefüggő gráf A gráf összefüggő, ha bármely két pontja közt létezik séta
Komponens Valamely gráf két csúcsa egy komponensben helyzekedik el, ha egyikből a másikba vezet séta.
,,Összefüggő részgráf”
Szabályos testek Azokat a konvex poliédereket, melyeknek minden lapja egybevágó sokszöglap, és minden lapszöge egynelő, szabályos testeknek nevezzük.
Vonal Olyan séta, melyben minden él legfeljebb 1-szer szerepel.
Út Olyan séta, melyben minden csúcs legfeljebb 1-szer szerepel.
Euler-vonal Olyan vonal, melyben minden él szerepel.
Fa Olyan gráf, mely az 1 csúcsú üres gráfból áthajtással (+1 csúcs hozzáfűzésével) felépíthető.
Erdő Olyan gráf, melynek minden komponense fa.
Kör Olyan vonal, melynek kezdő- és végpontja megegyezik.
Euler-kör Egy gráf Euler-köre olyan zárt élsorozat, amely a gráf összes élét pontosan egyszer tartalmazza.
Tételek neve/felhasználása Tétel
Csókolózni legjobb édes kettesben… Bármely síkgráf esetén: csúcsok + lapok = élek + komponensek (száma)
(c+l=é+k)
CSLÉK összefüggő síkgráfokra csúcsok + lapok = élek + 1 (c+l=é+1)
CSLÉK konvex poliéderekre csúcsok + lapok = élek + 2 (c+l=é+2)
Segédtétel: Bármely konvex poliéder síkja síkgráf.
Segédtétel bizonyítása: Nyújtható lapokkal egy lapot kivágva bizonyítunk.
Teljes gráf éleinek száma n(n-1)2
Fáry-Wagner tétel Minden egyszerű síkgráf lerajzolható síkra úgy, hogy élei egyenes szakaszok legyenek.
F-W t. indirekt bizonyítása Fizikai úton, lásd füzet!
Csúcs-fokszám a gráfban ∑Csúcsok x ∑Fokszám = 2x∑Élek
Fokszám-él arány Élek száma = ∑fokszám/2, így ∑fokszám = 2 x élek száma
Ennek következményei:
Gráfban csúcsok száma Minden gráfban a páratlan fokszámú csúcsok száma páros.
Egyszerű gráfban mindig létezik két azonos fokszámú csúcs.
Poliéder tulajdonságai Minden poliédernek van két azonos fokszámú csúcsa.
Minden poliédernek van két azonos oldalszámú lapja. (?)
Platóni testek Mindösszesen öt féle szabályos test létezik.
P. t. bizonyítása Euler-tétel alapján (Cs + l = é + 2)
P. t. bizonyítása (Mari néni) Négy eset:
I. ha háromszöglapok határolják
II. ha négyszöglapok határolják
III. ha ötszöglapok határolják
IV. ha hatszöglapok határolják
Mindnél: Vesszük a síklapot, meghatározzuk annak belső szögeit (amelyek egyenlőek), majd addig növeljük az egy pontba futó élek számát, amíg már nem tudunk többet hozzáadni amiatt, mert a 360°-ot nem lehet több, vagy a hozzáadott szögek összegével megegyező egyenlő részre osztani.
Euler-vonal összefüggő gráfban Egy összefüggő gráfnak pontosan akkor van Euler-vonala, ha minden csúcsfoka páros, vagy pontosan két foka páratlan.
Bizonyítás: Tfh.: a páratlan fokszámú csúcsok száma 0 vagy 2.
Vegyünk egy, a két páratlan fokszámú csúcsot összekötő vonalat.
Ha ez nem euler-vonal, akkor van olyan páros fokszámú csúcs, melynek még nem minden élén haladtam át.
Ebből a csúcsból indítható vonalnövelés, mely ugyanebbe a csúcsba ér vissza és legalább 1 élt tartalmaz. (Ez azért lehet, mert véges számú élünk van.) Így amikor már nem tudunk vonalat növelni, Euler-vonalat kapunk.
Fa csúcsai & élei Élek = Csúcsok - 1 (é=c-1)
A fa maximális, körmentes gráf adott csúcshalmazon. Bármely 2 csúcs között új élt felvéve új vonalat kapunk a 2 csúcs között, így kört kapunk. Tehát: az eredeti gráf körmentes, tehát fa.
A fa minimális összefüggő gráf adott csúcshalmazon. Biz.: A fa trivi körmentes. Így minden két csúcs között egy él fut, tehát bármelyik elvételével a fa 2 komponensre esik szét.
Bizonyítás A fa az olyan gráf, mely az 1 csúcsú üres gráfból áthajtással (1 éllel összekötött csúcs hozzáadásával) felépíthető.
K komponensű erdő élei Élek = Csúcsok - komponensek (c-k=é)
Szűcs-Gyires egyenlőtlenség / Rendezési tétel ∑ a(i) x b(i), n elemre akkor minimális, ha a, …, a(n) és b, …, b(n) egyike növekvő, másika csökkenő sorrendben rendezett.
Nagy gráfépítő metódus a fokszámok ellenőrzésére 1. Fokszámok növekvő sorrendbe tétele
  1. A legnagyobb fokszámú csúcs elhagyása, kisebb gráfot létrehozva (1-1 , összesen megfelelő mennyiségű fokszám levonásával)
  2. Amikor 1 kivételével csak 0-k maradnak, visszafele gráfépítés |