Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Bizonyítsuk be, hogy minden v...

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.?

Figyelt kérdés

2022. márc. 24. 18:00
 1/3 anonim ***** válasza:
18%

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.

2022. márc. 24. 20:11
Hasznos számodra ez a válasz?
 2/3 Baluba ***** válasza:
90%

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ó.

2022. márc. 24. 20:20
Hasznos számodra ez a válasz?
 3/3 krwkco ***** válasza:

#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.

2022. márc. 24. 20:28
Hasznos számodra ez a válasz?

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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!