- 1. feladat F M
Mutassuk meg, hogy egy minden pontot lefedő
minimális élrendszer diszjunkt csillagokból áll.
- 2. feladat F M
Alkalmazhatjuk a Menger tételt (6.39). Egy
közvetlen bizonyításhoz tekintsük a
G
egy minimális
G
′
részgráfját, melyre
τ
(
G
′
)
=
τ
(
G
)
, és mutassuk meg, hogy
G
′
független élekből áll.
- 3. feladat F M
Az
F
minden
A
-beli
y
pontjából kiindul egy
y
-t
A
1
-gyel összekötő,
M
-re nézve alternáló út.
- 4. feladat F M
A közvetlen bizonyításhoz alkalmazzunk indukciót
|
A
|
-ra; keressünk olyan
∅
≠
A
1
⊂
A
részhalmazt, melyre
|
Γ
(
A
1
)
|
=
|
A
1
|
.
- 5. feladat F M
Érveljünk a 7.4 első megoldásához
hasonlóan.
- 6. feladat F M
(a) Vegyük észre, hogy
(b) Tekintsünk egy minimális
G
1
részgráfot, melyre
V
(
G
1
)
=
V
(
G
)
és teljesül a (2) tulajdonság. Vegyük
észre, hogy (1) azt jelenti, hogy az egy-elemű halmazok
egyenlőséggel elégítik ki (2)-t.
- 7. feladat F M
Az (i)
⇒
(iii)
⇒
(ii)
⇒
(i) implikációk könnyen
beláthatók.
- 8. feladat F M
Az „akkor” irány könnyen belátható az előző
eredmény segítségével. A másik irányhoz rögzítsünk egy
F
1-faktort, az
F
egy éle legyen
G
0
, és válasszuk az
F
-re nézve alternáló
P
1
,
…
,
P
k
utakat (vö. 6.28 megoldásával).
- 9. feladat F M
Az előző feladatban szereplő
P
k
nem állhat egyetlen élből!
- 10. feladat F M
Először bizonyítsuk ezt
r
-reguláris gráfokra. Mutassuk meg,
hogy
G
-ben van 1-faktor, és távolítsuk el
ennek éleit.
- 11. feladat F M
Osszunk fel minden
x
pontot
d
(
x
)
k
k
fokú ponttá, és ha szükséges, még egy
d
(
x
)
−
k
d
(
x
)
k
fokú ponttá.
- 12. feladat F M
Használjuk fel 7.11-et
k
=
r
-rel.
- 13. feladat F M
Definiáljunk egy
G
1
gráfot
V
(
G
)
-n, két pontját akkor és csak akkor
kötve össze, ha
G
-ben egynél több éllel vannak
összekötve. Mely
r
értékek esetén képzelhető el, hogy
G
1
nem teljesíti a 7.4b-ben adott
feltételt?
- 14. feladat F M
Annak bizonyításához, hogy nem kerülhetünk
végtelen ciklusba, tekintsük az összes olyan élt,
melyen
x
végtelen sokszor áthalad és mutassuk
meg, hogy minden pont legfeljebb két ilyennel
szomszédos.
- 15. feladat F M
Különböztessük meg az elemi és a nem-elemi
gráfokat.
- 16. feladat F M
Vezessük vissza a 7.2 megoldásához hasonló
hálózati folyam-problémára.
- 17. feladat F M
Ilyen méretű
G
′
-be ágyazás egyértelmű. Annak
bizonyítására, hogy kisebb méretű
G
′
nem felelne meg, számoljuk meg a
G
egy szín-osztályát elhagyó éleket két
különböző módszerrel.
- 18. feladat F M
Azt kell megmutatni, hogy ha
G
˜
V
(
G
)
ponthalmazú páros gráf, ahol
x
∈
A
akkor és csak akkor van összekötve
y
∈
B
-vel, ha nem szomszédosak
G
-ben, akkor
G
˜
-ben van
(
n
−
2
d
)
-faktor.
- 19. feladat F M
Konstruáljunk egy
G
páros gráfot az
{
u
1
,
…
,
u
n
,
v
1
,
…
,
v
n
}
pontokon, ahol
u
i
akkor és csak akkor szomszédos
v
j
-vel, ha
a
i
j
>
0
. Azt kell belátnunk, hogy ebben a
páros gráfban van 1-faktor.
- 20. feladat F M
(a) Ha
G
-ben van 1-faktor, az ennek megfelelő
kifejtési tag nem eshet ki, mivel a mátrix nem-nulla
elemei algebrailag függetlenek. (b) Ha
G
-ben nincsen 1-faktor, akkor
(
a
i
j
)
oszlopai lineárisan összefüggők.
Tekintsük a lineárisan összefüggő oszlopok egy
minimális halmazát.
- 21. feladat F M
Ha
G
páros, a (
∗
) feltételek nem lineárisan
függetlenek.
- 22. feladat F M
Tegyük fel, hogy nem. Legyen
F
maximális párosítás és
u
,
v
két
F
-en kívüli pont. Hány él kötheti
{
u
,
v
}
-t bármely
F
-beli élhez?
- 23. feladat F M
Tekintsünk egy
F
maximális párosítást, melynek a lehető
legtöbb közös éle van
F
0
-lal.
- 24. feladat F M
(a) Alkalmazzunk indukciót
k
-ra. (b) Tekintsük a 6.27-ben adott
dekompozíciót. 6.30-at szintén alkalmazhatjuk. (c)
Használjuk a (b) következő élesítését: Ha
G
-ben egyetlenegy
F
1-faktor van, akkor
G
-nek van olyan elvágóéle, mely
F
-beli.
- 25. feladat F M
Tekintsünk egy
F
maximális párosítást és válasszunk egy
élt minden
F
által le nem fedett pontból.
- 26. feladat F M
Az
x
és
y
közötti távolságra vonatkozó
indukcióval bizonyítsuk be, hogy
ν
(
G
−
x
−
y
)
<
ν
(
G
)
minden
x
≠
y
∈
V
(
G
)
esetén.
- 27. feladat F M
(a)
δ
(
G
)
≥
max
…
könnyű. A
≤
belátásához alkalmazzunk indukciót és
az előző eredményt. (b) triviális (a)-ból.
- 28. feladat F M
(a) Azt kell belátnunk, hogy a „szomszédosság”
ekvivalencia-reláció
G
−
V
1
-ben. (b) Élek hozzáadása nem zavarja
a tételben megfogalmazott egyenlőtlenségeket.
- 29. feladat F M
(a) Alkalmazzuk Tutte tételét. (b) Egy
3-reguláris gráf elvágó-élét minden 1-faktornak
tartalmaznia kell.
- 30. feladat F M
Tutte feltétele teljesül. Ez következik abból, ha
megszámoljuk az éleket és az elhagyott éleket a 7.29a
megoldásához hasonló módon.
- 31. feladat F M
Érveljünk a 7.8-hoz hasonlóan,
P
0
,
P
1
,
…
,
P
k
utakat egyenként választva úgy, hogy
egy adott
F
maximális párosításra nézve
alternálóak legyenek.
- 32. feladat F M
(a) Legyen
x
∈
A
G
és
z
∈
D
G
az
x
egy szomszédja. Indirekten feltéve,
hogy
y
∉
D
G
, de
G
−
x
valamely
M
′
maximális párosítása kihagyja
y
-t, tekintsük a
G
egy
z
-t kihagyó
M
maximális párosítását, és nézzük
M
∪
M
′
-t. (b) Hagyjuk el
A
G
pontjait (a) felhasználásával. (c)-től
(e)-ig használjuk (a)-t és (b)-t.
- 33. feladat F M
G
′
bármely
M
0
párosításából egy
|
M
0
|
+
k
élű
G
-beli párosítást kapunk. A másik irány
bizonyításához tekintsük az előző feladatban leírt
Gallai–Edmonds struktúrát.
- 34. feladat F M
Ha két különböző komponensbeli külső pont
szomszédos, akkor egy 7.33 szerinti páratlan kört
kapunk. Egyébként hagyjuk el a belső pontokat.
- 35. feladat F M
Tekintsük a 7.32-beli
D
G
halmaz komponenseit és érveljünk a
7.29-hez hasonlóan.
- 36. feladat F M
(a) Legyen
F
egy maximális párosítás és
x
egy
F
által le nem fedett pont. (b)
Keressünk egy olyan
e
élt, melyre
e
-t tartalmazza legalább egy, de nem
minden 1-faktor, és
G
−
e
2-összefüggő (vö. 6.36).
- 37. feladat F M
Az könnyen látható, hogy egyetlen 2-párosítás sem
lehet nagyobb az adott értéknél. Ilyen méretű
2-párosítás kereséséhez vegyük a
G
-t két példányban,
G
és
G
′
, ahol
V
(
G
)
=
{
v
1
,
…
,
v
n
}
és
V
(
G
′
)
=
{
v
1
′
,
…
,
v
n
′
}
, és definiáljunk egy
G
0
páros gráfot úgy, hogy
v
i
-t akkor és csak akkor kötjük össze
v
j
′
-vel, ha
(
v
i
,
v
j
)
∈
E
(
G
)
.
- 38. feladat F M
Először vegyük a faktor-kritikus gráfokat, majd
alkalmazzuk a Gallai–Edmonds struktúra-tételt
(7.32).
- 39. feladat F M
Tekintsük a
G
egy Euler-vonalát.
- 40. feladat F M
Nézzünk egy pszeudoszimmetrikus irányítást (5.13)
és bontsunk fel minden pontot két ponttá, a bejövő és a
kimenő élek szétválasztásával. Alkalmazzuk 7.10-et erre
a páros gráfra.
- 41. feladat F M
Vezessük vissza Euler-gráfra a problémát: vegyünk
fel egy új
x
pontot és kössük össze minden páratlan
fokszámú ponttal.
- 42. feladat F M
(a) A pontok számának párosnak kell lenni! (b)
G
egy 2-szeresen összefüggő 3-reguláris
gráf összehúzásának eredménye.
- 43. feladat F M
(a) Helyettesítsünk minden pontot
f
(
x
)
független ponttal. (b) Ha
f
(
x
)
=
1
bármely él legalább egyik végpontjára,
akkor egy
f
-párosítás egyben egy
f
-faktor.
- 44. feladat F M
Bontsunk fel minden
x
pontot két
x
′
,
x
″
pontra, melyek a bejövő illetve kimenő
élekhez illeszkednek.
- 45. feladat F M
Osszunk fel minden élt és definiáljuk
f
-et 1-nek a létrejövő új pontokon.
Keressük az új gráf egy
f
-faktorát.
- 46. feladat F M
Alkalmazzunk indukciót.
- 47. feladat F M
Alkalmazzunk indukciót.
- 48. feladat F M
Mutassuk meg, hogy a
d
1
,
…
,
d
n
−
2
,
d
n
−
1
−
1
,
d
n
−
1
sorozat kielégíti ugyanazokat a
feltételeket.
- 49. feladat F M
Használjuk 7.44-et.
- 50. feladat F M
Transzformáljuk a
d
1
,
…
,
d
n
fokszámokkal rendelkező
G
gráfot olyan gráfba, melynek fokszámai
ugyanezek, és melyben
v
n
szomszédos
v
n
−
d
n
,
…
,
v
n
−
1
-gyel.
- 51. feladat F M
(a) Válasszuk
H
-t a lehető legtöbb ellentétesen
irányított élpárral. Mutassuk meg, hogy
H
azon élei, melyek ellentettje nem
H
-beli, nem alkothatnak sem páros
irányított kört, sem két diszjunkt páratlan irányított
kört. (b) (a)-ból és 7.49-ből triviális.
- 52. feladat F M
A feltétel elégségességének bizonyításához
tekintsünk egy gráfot ezekkel a fokszámokkal és
csökkentsük egyenként a komponensek számát.
- 53. feladat F M
Legyen
G
egy olyan gráf a
V
=
{
v
1
,
…
,
v
n
}
ponthalmazon, melyben
d
G
(
v
i
)
=
d
i
, és
G
′
egy másik, melyben
d
G
′
(
v
i
)
=
d
i
−
1
. Válasszuk
G
′
-t és
G
-t a lehető „legközelebbinek”.