Bevezetés a számításelméletbe II.

3. gyakorlat, 2006. március 1.

                             Koblinger Egmont <egmont@cs.bme.hu>

Menger-tételek, többszörös összefüggőség

22. Adjuk meg az n függvényében, hogy hányszorosan összefüggő, illetve hányszorosan élösszefüggő K_{n} és K_{n,n}.

23. Mutassuk meg, hogy a k-szoros pontösszefüggőségből következik a k-szoros élösszefüggőség, de ugyanez visszafelé már nem teljesül.

24. Bizonyítsuk be, hogy ha egy k-szorosan összefüggő gráfhoz hozzáveszünk egy új, legalább k fokú csúcsot, akkor az k-szorosan összefüggő marad.

25. Mutassuk meg, hogy egy k-szorosan összefüggő n pontú gráfnak legalább \frac{kn}{2} éle van.

26. Bizonyítsuk be, hogy ha egy gráf legalább \frac{n}{2}-szeresen összefüggő, akkor van benne Hamilton kör.

27. Mutassunk olyan gráfot, amely kétszeresen összefüggő, háromszorosan élösszefüggő és legalább négy él megy ki minden pontból.

28. Mutassunk olyan gráfot, amely kétszeresen, de nem háromszorosan összefüggő, háromszorosan, de nem négyszeresen élösszefüggő és legalább négy él megy ki minden pontból.

29. Egy gráf akkor és csak akkor 2-szeresen összefüggő, ha bármely két pontján/élén keresztül vezet kör.

30. Igazoljuk, hogy egy G(V, E) gráf akkor és csak akkor kétszeresen összefüggő, ha bármely v ∈ V és e ∈ E-re van olyan kör a gráfban, mely átmegy v-n és e-n.

31. Egy k-szorosan összefüggő gráfban kijelölünk k darab A_{i} csúcsot, és k darab B_{j} csúcsot. Legalább hány közös belső pont nélküli A_{i} − B_{j} út létezik?

32. Legyen G egy kétszeresen összefüggő gráf. Súlyozhatók-e G élei úgy, hogy nem minden súly egyenlő, viszont G minden feszítőfájának a súlya azonos legyen?

33. Legyen k ≤ n − 1. Bizonyítsuk be, hogy ha egy n pontú egyszerű gráfban minden pont foka legalább \frac{n+k−2}{2}, akkor a gráf k-szorosan összefüggő.

34. Bizonyítsuk be, hogy 3-reguláris gráfokra az él- és pontösszefüggőségi számok megegyeznek.