- 1. feladat F M
Egy új él felvétele legfeljebb eggyel csökkenti a
komponensek számát.
- 2. feladat F M
(a) Legyenek
T
1
,
…
,
T
c
(
G
1
)
a
G
1
komponensei,
S
1
,
…
,
S
c
(
G
2
)
a
G
2
komponensei. Konstruáljunk olyan
G
∗
gráfot a
V
(
G
∗
)
=
{
t
1
,
…
,
t
c
(
G
1
)
s
1
,
…
,
s
c
(
G
2
)
}
ponthalmazon, melyben
t
i
és
s
j
akkor és csak akkor van összekötve, ha
T
i
∩
S
j
≠
∅
, majd vizsgáljuk ezen gráf
komponenseit. (b) Adjuk hozzá
V
(
G
1
)
−
V
(
G
2
)
pontjait
G
2
-höz izolált pontokként.
- 3. feladat F M
Legyen
x
i
foka
d
i
. Vegyük a
G
egy
x
n
-t nem tartalmazó
G
1
komponensét; ennek kizárólag
|
V
(
G
1
)
|
-nél kisebb fokszámú pontjai
vannak!
- 4. feladat F M
Ha
G
1
tartalmaz mondjuk páratlan kört és
összefüggő, lássuk be, hogy
G
1
-ben bármely két ponthoz találunk
azokat összekötő tetszőlegesen hosszú sétát, majd
használjuk fel ezt a tényt.
- 5. feladat F M
Vö. 5.1b.
- 6. feladat F M
(a) Tekintsünk egy leghosszabb utat. (b)
Tekintsük egy leghosszabb út egy végpontját. (c) Ha nem
létezik ilyen pár, akkor egy feszítő fa végpontjainak
teljes részgráfot kell alkotniuk.
- 7. feladat F M
(a) Minden lépésben megnövelhetjük
T
1
és
T
2
közös éleinek számát. (b) Alkalmazzunk
„visszafelé” indukciót
T
1
és
T
2
egy közös részfájának élszáma
szerint.
- 8. feladat F M
(a)–(b) Használjuk fel 6.7b-t.
- 9. feladat F M
Annak bizonyításához, hogy létezik
(
a
,
b
)
-út, tekintsük az
a
-ból elérhető pontok
X
halmazát.
- 10. feladat F M
Húzzuk össze a piros éleket, és hagyjuk el a
zöldeket.
- 11. feladat F M
(a)–(b)–(c). Ha
F
olyan minimális halmaz, melynek
elhagyása (összehúzása) a kívánt tulajdonsággal
rendelkező irányított gráfot eredményez, akkor
F
megfordítása szintén ilyen gráfot
ad.
(b) Nézzük először az
|
F
|
=
1
esetet.
(c) Először azt mutassuk meg, hogy egy irányított
körmentes
G
gráf pontjait sorbarendezhetjük úgy,
hogy minden él kisebb számpontból nagyobb számúba
mutasson.
- 12. feladat F M
Annak bizonyításához, hogy minden erősen
összefüggő turnament tartalmaz irányított
Hamilton-kört, tekintsünk egy nem bővíthető irányított
kört.
- 13. feladat F M
Vegyünk egy leghosszabb olyan irányított kört,
mely nem Hamilton-kör.
- 14. feladat F M
Fordítsuk meg
F
éleit.
- 15. feladat F M
Tekintsünk egy valódi részfát, melyet
ϕ
önmagába képez le.
- 16. feladat F M
Tekintsük a metszet két pontját és az őket
összekötő utat.
- 17. feladat F M
(a) Feltéve, hogy
P
1
és
P
2
diszjunkt maximális utak, tekintsünk
egy
Q
(
P
1
,
P
2
)
-utat. (b) Egy rögzített maximális út
középpontját minden más maximális út
tartalmazza.
- 18. feladat F M
Indukciót alkalmazunk
k
-ra és
n
-re. Az első esetben keressünk egy
G
k
-t és
G
1
∩
…
∩
G
k
−
1
-tól elválasztó élt.
- 19. feladat F M
Csak (c) nem triviális.
d
(
x
,
y
)
esetében tekintsünk egy minimális
(
x
,
y
)
-utat és egy minimális
(
y
,
z
)
-utat;
D
(
x
,
y
)
esetében tekintsünk egy nem bővíthető
(
x
,
z
)
-utat.
- 20. feladat F M
Vegyünk egy élt és számoljuk meg, hogy hány
(
p
i
,
p
j
)
típusú, hány
(
p
i
,
q
j
)
típusú és hány
(
q
i
,
q
j
)
típusú út tartalmazza.
- 21. feladat F M
(a) Mutassuk meg, hogy minden elsőfokú pontot
eltávolítva
d
˜
(
x
)
minden megmaradó pontra eggyel
csökken. (b) Vegyünk egy leghosszabb
x
-ből induló utat.
- 22. feladat F M
(a)
x
-ből
y
-ba haladva mely
z
pontokra nő, illetve csökken
d
(
x
,
z
)
? (b) könnyen adódik
(
a
)
-ból. (c) Vegyünk egy hosszú utat egy
nagy „legyezővel” valamelyik végén.
- 23. feladat F M
∑
x
,
y
d
(
x
,
y
)
minimumának meghatározásához vegyük
észre, hogy pontosan
n
−
1
tag egyenlő 1-gyel; lehet-e az összes
többi 2-vel egyenlő? Másrészről mutassuk meg, hogy
s
(
x
)
akkor maximális, ha
G
egy út és
x
egy végpontja.
- 24. feladat F M
Rendeljünk hozzá
k
kivételével az összes ponthoz egy
k
hosszú, az adott pontból induló utat
úgy, hogy különböző pontokhoz különböző utak
tartozzanak.
- 25. feladat F M
Legyen
G
az algoritmus által generált fa,
H
pedig egy minimális költségű fa,
melynek
G
-vel a lehető legtöbb közös éle van.
Feltéve, hogy
G
≠
H
, tekintsünk egy
G
-beli, de nem
H
-beli élt.
- 26. feladat F M
Érveljünk 6.25-höz hasonlóan.
- 27. feladat F M
Két él akkor és csak akkor ekvivalens, ha
ugyanazok a körök mennek át rajtuk.
- 28. feladat F M
Válasszuk a
G
1
,
…
,
G
i
részgráfokat úgy, hogy kielégítsék a
feltételt és mutassuk meg, hogy ha
G
1
∪
…
∪
G
i
≠
G
, akkor tudunk választani
G
i
+
1
-t.
- 29. feladat F M
A nem triviális rész az, hogy ha
G
2-szeresen élösszefüggő, akkor létezik
megfelelő irányítása. Használjuk
6.27-et vagy
6.28-at.
- 30. feladat F M
Keressünk olyan kört, melyre egy kivételével
minden adott él jól illeszkedik és húzzuk össze, majd
folytassuk indukcióval a bizonyítást.
- 31. feladat F M
Annak bizonyításához, hogy ha
e
1
és
e
2
egy
C
1
körön vannak,
e
2
és
e
3
pedig egy
C
2
körön, akkor
e
1
és
e
3
szintén rajta vannak egy közös körön,
tekintsük
C
1
és
C
2
azon közös pontjait, melyek
e
3
-hoz legközelebb vannak
C
2
-n mindkét irányban.
- 32. feladat F M
Az (i)
⇒
(iii)
⇒
(ii)
⇒
(i) ciklusban csak az első lépés nem
triviális. Bizonyítsuk (iii)-t először két szomszédos
élre!
- 33. feladat F M
Keressünk és alkalmazzunk
G
-re egy 6.27-hez hasonló konstrukciót.
Egy másik lehetőség az, ha kiválasztunk valamely két
pontot összekötő 3 utat,
P
1
-et,
P
2
-t és
P
3
-at úgy, hogy
P
1
a lehető legrövidebb, és megmutatjuk,
hogy
P
1
eleget tesz a követelményeknek.
- 34. feladat F M
G
pontjait rendezzük olyan sorrendbe,
hogy
p
az első pont,
q
az utolsó és minden más pontból megy
él kisebb és nagyobb sorszámú pontba egyaránt.
- 35. feladat F M
Egy kör húrját a 2-szeresen összefüggőség
megsértése nélkül elhagyhatjuk.
- 36. feladat F M
Válasszunk egy
x
és
y
végpontú
(
C
,
C
)
-utat,
P
-t, melyre az
x
-et és
y
-t
C
-n összekötő
R
ív minimális. Ekkor
x
szomszédja
R
-en másodfokú.
- 37. feladat F M
Ha
G
′
összefüggő lenne,
G
tartalmazna egy kört, melynek
másodfokú pontjai egy ívet alkotnának.
- 38. feladat F M
Azonosítsuk két izomorf fa megfelelő
végpontjait.
- 39. feladat F M
(a) Alkalmazzunk indukciót
|
E
(
G
)
|
-re. Ha van egy
S
⊆
V
(
G
)
, mely egy
k
-elemű
(
a
,
b
)
-vágást határoz meg, és
|
S
|
≥
2
,
|
V
(
G
)
−
S
|
≥
2
, akkor alkalmazzuk rendre az
S
és
V
(
G
)
−
S
összehúzásával kapott gráfokra az
indukciós feltételt. (b) Osszunk fel minden
x
≠
a
,
b
pontot
x
1
és
x
2
pontokra, majd kössük össze
x
1
-et és
x
2
-t, és
x
2
-t akkor és csak akkor kössük össze
y
1
-gyel, ha
x
össze volt kötve
y
-nal. (c) Helyettesítsünk minden
(irányítatlan) élt két ellentétesen irányított
éllel.
- 40. feladat F M
Vegyünk két új pontot,
a
-t és
b
-t; kössük össze
a
-t
A
minden pontjával és
b
-t
B
minden pontjával.
- 41. feladat F M
Egy közös általánosítás a következő. Ha
A
,
B
⊆
V
(
G
)
diszjunkt halmazok, minden
x
ponthoz hozzárendelünk egy pozitív
egész
w
(
x
)
„kapacitást” és minden olyan
S
ponthalmazra, mely minden
(
A
,
B
)
-utat metsz
akkor van
k
olyan
(
A
,
B
)
-út, hogy minden
x
pontot közülük legfeljebb
w
(
x
)
tartalmaz.
- 42. feladat F M
Válasszunk
k
független
(
a
,
B
)
-utat,
R
1
,
…
,
R
i
-t úgy, hogy
R
t
ugyanott indul, ahol
P
t
végződik és
minimális.
- 43. feladat F M
Válasszuk
B
=
V
(
P
0
)
-t és alkalmazzuk 6.42-t.
- 44. feladat F M
A Menger tétel ismeretében könnyű belátni, hogy
G
két teljes gráf egyesítése lesz,
melyeknek
k
közös pontja van,
a
∈
V
(
G
1
)
,
b
∈
V
(
G
2
)
, és
a
,
b
∉
V
(
G
1
∩
G
2
)
. Ahhoz, hogy ezt a Menger tétel
felhasználása nélkül bizonyítsuk, mutassuk meg, hogy
minden pont össze van kötve
a
-val vagy
b
-vel és a mindkettővel összekötött
pontok elválasztják az
(
a
,
b
)
utakat.
- 45. feladat F M
Egyik sem igaz.
- 46. feladat F M
Használjuk a Menger tételt.
- 47. feladat F M
(i)-hez: Hagyjuk el egy
(
a
,
b
)
-út (ha van ilyen) éleit és
alkalmazzuk 6.46-ot.
- 48. feladat F M
Mindkét oldalon számoljuk meg az élek
adalékát.
- 49. feladat F M
Tekintsünk egy
X
halmazt, melyre
δ
G
(
X
)
=
k
és
|
X
|
minimális.
- 50. feladat F M
Húzzuk össze a nem
F
1
,
…
,
F
m
-beli éleket és nézzük az így kapott
gráfot.
- 51. feladat F M
Legyen
U
⊂
V
(
G
)
−
{
x
}
egy maximális halmaz, melyre
δ
G
(
U
)
=
k
és az
x
egy bizonyos
y
szomszédja
U
-beli. Mutassuk meg, hogy létezik
x
-nek nem
U
-beli
z
szomszédja.
- 52. feladat F M
Alkalmazzuk újra és újra az előző
„pont-felosztást”, amíg
x
el nem tűnik.
- 53. feladat F M
Használjuk 6.48c-t
6.48a helyett.
- 54. feladat F M
(a) triviális. (b)-hez keressünk egy
2
k
fokú pontot és „osszuk fel” úgy, mint
6.52 megoldásában.
- 55. feladat F M
Tekintsünk egy négyszöget.
- 56. feladat F M
(a) Mutassuk meg, hogy
α
+
β
él-diszjunkt
{
a
,
b
}
-t
{
a
′
,
b
′
}
-hez kötő út van, és ezek közül
pontosan
α
kezdődik
a
-ban és pontosan
α
(esetleg valamely más
α
) végződik
a
′
-ben. (b) Alkalmazzunk 6.46-hoz és
6.47-hez hasonló érvelést.
- 57. feladat F M
Keressünk síkbarajzolható példát.
- 58. feladat F M
C
nyilvánvalóan lefogja az
(
a
,
b
)
utakat. Annak bizonyításához, hogy
|
C
|
=
k
, tekintsük a
b
-ből
(
b
,
A
∪
B
)
-úton elérhető pontok
D
halmazát; mutassuk meg, hogy
Másik lehetőség a Menger-tétel
alkalmazása.
- 59. feladat F M
Ha
(
x
,
y
)
a
H
egy éle és
T
a
G
−
(
x
,
y
)
egy
(
k
−
1
)
elemű elvágó ponthalmaza, akkor
T
∩
V
(
H
)
lefogja
H
−
(
x
,
y
)
-t.
- 60. feladat F M
(a) Tételezzük fel, hogy az állítás hamis. Legyen
G
−
A
=
G
1
∪
G
2
,
G
−
B
=
G
3
∪
G
4
,
(
G
1
∩
G
2
=
G
3
∩
G
4
=
∅
)
és tegyük fel, hogy pl.
G
1
∩
G
3
≠
∅
és
V
(
G
1
)
∩
B
≠
∅
. Legyen
a
∈
G
1
∩
G
3
, és legyen
C
az
A
∪
B
a
-ból
(
a
,
A
∪
B
)
-úton elérhető pontjainak halmaza.
Mutassuk meg, hogy
(b) Bizonyítsuk be, hogy az (a)-ban
definiált
G
1
1-elemű halmaz.
- 61. feladat F M
Válasszuk
e
=
(
a
,
b
)
-t és tegyük fel, hogy mind
G
∕
e
, mind
G
−
e
csak 2-szeresen összefüggő. Mutassuk
meg, hogy
(a) van két olyan
x
,
y
pont
G
−
e
-ben, melyek elválasztják
a
,
b
-t,
(b) van olyan
u
pont
G
-ben, melyre
{
a
,
b
,
u
}
elválasztja
x
,
y
-t,
(c) ha
{
x
,
y
}
elválasztja
a
-t
u
-tól, akkor
x
,
y
és
b
az
a
kizárólagos szomszédai.
- 62. feladat F M
Mutassuk meg, hogy ha
G
egyszerű gráf és
e
a
G
egy éle, mely legalább
k
fokú pontokat köt össze, továbbá
G
∕
e
k
-szorosan összefüggő, akkor
G
is az.
- 63. feladat F M
Alkalmazzunk indukciót a kör hosszára.
- 64. feladat F M
Legyen
a
egy harmadfokú fokú pont, mely
b
1
-gyel,
b
2
-vel és
b
3
-mal van összekötve. Mutassuk meg,
hogy ha
G
≠
K
4
, akkor van
b
i
+
1
-et és
b
i
+
2
-t (
i
=
1
,
2
,
3
;
b
j
+
3
=
b
j
) elválasztó
u
i
pont
G
−
a
−
b
i
-ben, majd használjuk fel ezt a
tényt.
- 65. feladat F M
Rajzoljunk egy olyan
T
fát a síkba, melynek nincsenek
másodfokú pontjai, és végpontjai a konvex burkán
vannak; majd vegyük hozzá a
C
konvex burok éleit. Lássuk be, hogy ez
a
G
gráf él-kritikusan 3-szorosan
összefüggő.
- 66. feladat F M
Alkalmazzunk indukciót
k
-ra. Ha
x
1
,
…
,
x
k
−
1
rajta vannak
C
-n, de
x
k
nem, vegyünk
k
független
(
x
k
,
C
)
-utat.
- 67. feladat F M
Tegyük fel, hogy egyetlen kör sem tartalmazza
mindhárom megadott élt. Keressünk egy kört, mely kettőt
tartalmaz közülük és a harmadikat nem érinti, és
vizsgáljuk meg a harmadik élt ezzel a körrel összekötő
utakat úgy, mint 6.66-ban.
- 68. feladat F M
Próbáljunk 6.66-nak megfelelően érvelni.
- 69. feladat F M
Mutassuk meg, hogy egy lap határának minden hídja
tartalmazza a kör összes pontját.
- 70. feladat F M
Legyen
f
∈
E
(
G
)
és válasszuk ki a
G
−
f
egy olyan
C
körét, melyre
C
-nek
f
-et tartalmazó
B
hídja nem bővíthető.
- 71. feladat F M
Tegyük fel, hogy
v
(
e
1
)
≥
…
≥
v
(
e
m
)
, ahol
E
(
G
)
=
{
e
1
,
…
,
e
m
}
, és nézzük az első olyan
k
indexet, melyre
{
e
1
,
…
,
e
k
}
tartalmaz
(
a
,
b
)
-utat.
- 72. feladat F M
Határozzunk meg egy olyan
ϕ
függvényt, melyre minden
x
ponthoz van
ϕ
(
x
)
értékű
(
a
,
x
)
-út.
- 73. feladat F M
Legyen a
C
vágás az
S
⊆
V
(
G
)
halmaz által meghatározva. Tekintsük a
következő kifejezést:
- 74. feladat F M
A bizonyítás nem triviális része olyan
f
(
a
,
b
)
-folyam és
C
(
a
,
b
)
-vágás keresése, melyre
Vegyünk egy
f
maximális értékű folyamot, mely eleget
tesz
f
≤
v
-nek. Minden
e
∈
E
(
G
)
-re bevezetünk egy új
e
′
élt azonos végpontokkal, de ellentétes
irányítással, majd legyen
Ezután nézzük azon
e
és
e
′
élek által meghatározott
G
1
irányított gráfot, melyeken
v
0
(
e
)
>
0
ill.
v
0
(
e
′
)
>
0
. Bizonyítsuk be, hogy
G
1
nem összefüggő
a
és
b
között.
- 75. feladat F M
(a) Legyen
ω
n
az
n
-edik lépésben a folyam-érték
növekménye; ekkor
∑
n
=
1
∞
ω
n
konvergens kell, hogy legyen.
Próbáljuk meg elérni, hogy
ω
n
=
α
n
legyen, ahol
α
<
1
. Hogyan változhat
f
k
(
e
)
értéke két egymást követő azonos
helyzet között? (b) Mutassuk meg, hogy ha elhagyjuk
azon éleket, melyeket a
P
k
és
P
k
+
1
utak különböző irányban használnak,
P
k
∪
P
k
+
1
még mindig tartalmaz két
(
a
,
b
)
-utat,
Q
1
-et és
Q
2
-t, melyekre
Q
1
∩
Q
2
⊆
P
k
∩
P
k
+
1
.
(c) Ha egy élt
P
k
és
P
k
+
l
ellentétes irányban használ, akkor
P
k
+
l
hosszabb
P
k
-nál.
- 76. feladat F M
Vezessünk be két új
a
0
,
b
0
pontot; kössük össze
a
0
-t minden olyan
x
ponttal, melyre
u
(
x
)
≥
0
és adjuk az új
e
élnek a
v
(
e
)
=
u
(
x
)
kapacitást; kössünk össze minden
x
pontot, melyre
u
(
x
)
<
0
b
0
-lal és adjuk az új
e
élnek a
v
(
e
)
=
−
u
(
x
)
kapacitást. A feladat ekvivalens az
eredményül kapott
G
1
gráfban egy megfelelő
(
a
0
,
b
0
)
-folyam keresésével.
- 77. feladat F M
(a) Helyettesítsünk minden
e
élt
v
(
e
)
párhuzamos éllel, és alkalmazzuk a
Menger tételt. (b) Mutassuk meg először racionális
v
(
e
)
kapacitások esetére olyan
f
(
e
)
≤
v
(
e
)
(
a
,
b
)
-folyam és
C
(
a
,
b
)
-vágás létezését, melyekre
- 78. feladat F M
Feltehetjük, hogy
k
=
2
. Tekintsünk egy olyan egész értékű
f
′
(
a
,
b
)
-folyamot, melyre
w
(
f
′
)
≥
w
1
,
f
′
(
e
)
≤
f
(
e
)
és
∑
e
f
′
(
e
)
minimális.