- 1. feladat Ö M
Ha egy gráfban minden pont foka legfeljebb
d
, akkor
- 2. feladat Ö M
Minden
G
gráf pontjai lefedhetők nem több, mint
α
G
pont-diszjunkt úttal.
- 3. feladat Ö M
Minden
G
gráf pontjai lefedhetők nem több, mint
α
G
pont-diszjunkt körrel, éllel és ponttal.
- 4*. feladat Ö M
Legyen
G
irányított gráf és
S
a
V
G
egy olyan részhalmaza, melyre vannak
S
pontjaiból induló diszjunkt (irányított)
V
G
-t lefedő utak. Mutassuk meg, hogy
S
-ből kiválasztható egy ugyanilyen tulajdonságú
S
0
részhalmaz, melyre
- 5. feladat Ö M
(a) Minden szimmetrikus irányított gráfnak van
magja.
(b) Minden körmentes
G
irányított gráfnak egyetlenegy magja van.
(c) Ha az irányított
G
gráf minden irányított köre páros hosszúságú,
akkor
G
-nek van magja.
- 6. feladat Ö M
Minden
T
turnamentben van olyan pont, melyből minden más
pont elérhető legfeljebb 2 hosszúságú irányított úton.
- 7. feladat Ö M
Minden
G
irányított gráf tartalmaz egy olyan
S
⊆
V
G
független halmazt, melyre minden pont elérhető
S
-ből legfeljebb 2 hosszúságú irányított
úton.
- 8. feladat Ö M
Legyen
G
irányított gráf. Az
A
és
B
játékos a következő játékot játssza. Kezdés
gyanánt
A
elfoglal egy tetszőleges pontot. Ezután felváltva
foglalnak el olyan újabb pontokat; az elfoglalt pontnak különböznie
kell a már elfoglaltaktól, és elérhető kell, hogy legyen az
ellenfél legutóbb elfoglalt ponttól. Az a játékos veszít, aki
először nem tud elfoglalni pontot.
(a) Tegyük fel, hogy
G
-ben nincsen irányított kör. Mutassuk meg, hogy
A
-nak van nyerő stratégiája, és határozzuk meg azon
pontok halmazát, melyekből érdemes kezdenie.
(b) Most ejtsük el azt a feltevést, hogy
G
irányított körmentes, de tegyük fel, hogy van egy
0 befokú
x
0
pontja (forrása). Mutassuk meg, hogy a kezdő
A
játékosnak még mindig van nyerő
stratégiája.
(c) Most legyen
G
tetszőleges irányított gráf. Mutassuk meg, hogy a
második játékosnak akkor és csak akkor van nyerő stratégiája, ha
G
minden erős komponensén van nyerő
stratégiája.
- 9. feladat (Folytatás) Ö M
Legyen
G
egy gráf (vagy ezzel ekvivalens módon egy
szimmetrikus irányított gráf). Mutassuk meg, hogy a kezdő
játékosnak akkor és csak akkor van nyerő stratégiája, ha
G
-ben van 1-faktor.
- 10. feladat Ö M
Legyen
T
1
,
…
,
T
k
maximális független halmazok egy
G
gráfban. Mutassuk meg, hogy
- 11. feladat Ö M
Legyenek
T
1
,
…
,
T
k
a
G
maximális független halmazai, és legyen
X
tetszőleges független halmaz. Legyen
Ekkor
- 12. feladat Ö M
Legyen
G
egy izolált pontot nem tartalmazó
α
-kritikus gráf. Ekkor minden
x
pontot tartalmaz legalább egy maximális független
halmaz, de nem mindegyik. Ha
x
és
y
két pont, melyek nem alkotnak
G
-ben komponenst, akkor van olyan maximális
független halmaz, mely pontosan egyiküket tartalmazza. Ha
x
és
y
szomszédosak, akkor van egy másik maximális
független halmaz, melybe egyiküket sem tartalmazza.
- 13. feladat Ö M
Egy
α
-kritikus gráf minden pontját egy teljes gráffal
helyettesítve ismét
α
-kritikus gráfot kapunk.
- 14. feladat Ö M
Minden gráf valamely
α
-kritikus gráf feszített részgráfja.
- 15. feladat Ö M
(a) Keressünk végtelen sok összefüggő
r
-reguláris
α
-kritikus gráfot (
r
≥
2
).
(b) Mely szabályos testek
α
-kritikusak?
- 16. feladat Ö M
Mely páros gráfok
α
-kritikusak?
- 17*. feladat Ö M
Egy
α
-kritikus gráf bármely két szomszédos élét
tartalmazza egy átlómentes páratlan kör.
- 18. feladat Ö M
Egy
α
-kritikus gráfnak nincsen teljes gráfot kifeszítő
elvágó ponthalmaza (speciálisan nincsen elvágópontja).
- 19*. feladat Ö M
(a) Legyen
G
1
és
G
2
összefüggő,
K
2
-től különböző
α
-kritikus gráfok. Osszuk fel a
G
1
valamely
x
pontját az
x
1
és
x
2
pontokra, hagyjuk el a
G
2
egy
y
1
,
y
2
élét, és azonosítsuk
x
i
-t
y
i
-vel. (Így például két háromszögből egy ötszög
lesz.) Mutassuk meg, hogy a kapott gráf
α
-kritikus.
(b) Mutassuk meg továbbá, hogy minden összefüggő, de nem
3-szorosan összefüggő
α
-kritikus gráf előállítható így.
- 20. feladat Ö M
Egy izolált pontot nem tartalmazó
α
-kritikus
G
gráfnak legalább
2
α
G
pontja van.
- 21. feladat Ö M
Egy
α
-kritikus gráfban minden független
X
ponthalmazra
|
Γ
X
|
≥
|
X
|
.
- 22. feladat Ö M
Legyen
X
az
α
-kritikus
G
gráf független ponthalmaza és
x
∈
X
. Ekkor
- 23. feladat Ö M
(a) Egy izolált pontot nem tartalmazó
n
pontú
α
-kritikus
G
gráf maximális fokszáma legfeljebb
n
−
2
α
G
+
1
.
(b) Egy
n
pontú
α
-kritikus
G
gráf éleinek száma legfeljebb
n
−
α
G
+
1
2
.
- 24*. feladat Ö M
Mely
α
-kritikus
G
gráfok regulárisak
|
V
G
|
−
2
α
G
+
1
fokszámmal?
- 25. feladat Ö M
Jellemezzük az összefüggő
α
-kritikus
G
gráfokat, melyekre
|
V
G
|
−
2
α
G
=
0
,
1
illetve
2
.
- 26. feladat Ö M
Tegyük fel, hogy
α
G
−
x
−
y
=
α
G
minden
x
,
y
∈
V
G
esetén és
|
V
G
|
=
2
α
G
+
1
. Mutassuk meg, hogy
G
egy páratlan kör.
- 27. feladat Ö M
Legyen
G
olyan gráf, melyre
α
G
−
{
x
,
y
,
z
}
=
α
G
minden
x
,
y
,
z
∈
V
G
esetén. Mutassuk meg, hogy vagy
|
V
G
|
≥
2
α
G
+
3
, vagy
G
≅
K
4
.