Bizonyítsuk be, hogy minden v ≥ 4 természetes számhoz létezik egy sík gráf, amelynek v csúcsa van, amelynek minden tartományát a C4 kör (ciklus) határol.?
Ha v=4, akkor triviális, maga a C4 kör teljesíti a feltételt.
Ha v=5, akkor rajzoljunk egy C4 kört, például egy négyzetet, ennek ötödik pontja legyen a négyzet középpontja, ezt összekötjük a négyzet csúcsaival, a behúzásokat hívjuk küllőknek. Kész is van a feltételeknek megfelelő gráf.
Ha v>=6, akkor az előbbi gráf küllőire akárhogyan elszórhatjuk a csúcsokat, a C4 mindig határolni fogja a belső tartományokat.
Mivel a külső, végtelen tartományt is C4 határolja, ezért a gráf összefüggő.
v=4 triviális, egy négyzet teljesíti a feltételt.
Teljes indukcióval tegyük föl, hogy valamely v=n-re már tudunk ilyen gráfot.
Ekkor v=n+1-re: vegyük az n-re jó gráf egy tetszőleges síkbarajzolását, és ennek a végtelen tartományát (de tetszőleges tartománnyal is működik). A v+1. csúcsot helyezzük el a végtelen tartományban, és kössük össze a végtelen tartományt határoló C4 két, nem szomszédos csúccsal, ez lesz a 2 új él. Ekkor az új gráf továbbra is síkgráf. A korábbi véges tartományok nem változtak, így továbbra is C4 határolja őket. Újonnan létrejött egy véges tartomány, amit szintén C4 határol, 4 csúcs az eredeti C4-ről és az új csúcs. Az új végtelen tartomány szintén C4, hasonló megfontolásból. Tehát az új gráf n+1 csúccsal is jó lesz, ezzel kész a teljes indukció.
#1
Nem úgy kell érteni a kérdést, hogy a gráf minden egyes tartományát (élekkel határolt üres területét) külön-külön C4 határolja?
Akkor úgy lehet bővíteni a C4 és a további gráfokat, hogy felrakunk egy külső csúcsot és két olyan külső csúccsal kötjük össze, amiknek a távolsága 2 élnyi.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!