- 1. feladat F M
(a) Mennyi a gráf fokszámainak összege? (b) A
fejezet címe félrevezető, alkalmazzunk 3-mal való
oszthatóságot. (c) Hogyan kapcsolódik egymáshoz az első
és az utolsó pont?
- 2. feladat F M
Használjuk az 5.1a megoldását.
- 3. feladat F M
Ha minden kör páros hosszú, akkor bármely két
x
és
y
közti út azonos paritású.
- 4. feladat F M
Ha bármely kör mentén az összmunka zérus, akkor
az
x
-ből
y
-ba jutáshoz szükséges munka nem függ
a választott úttól.
- 5. feladat F M
Ha van egy páros
C
kör, akkor
G
2-színezését kezdjük
C
-vel, majd ezt terjesszük ki.
- 6. feladat F M
Vegyük
G
egy maximális zárt vonalát és mutassuk
meg, hogy minden élt tartalmaz.
- 7. feladat F M
(a) 5.6 miatt triviális. (b) Vegyük észre, hogy
G
k
,
n
=
L
(
G
k
−
1
,
n
)
.
- 8. feladat F M
Ez ugyanazt jelenti, mint „
G
k
,
2
tartalmaz irányított
Hamilton-kört”.
- 9. feladat F M
Tekintsük egy Euler-vonal azon szakaszait, melyek
egy legalább 3 fokú
x
pont két egymást követő előfordulása
közt helyezkednek el.
- 10. feladat F M
Annak bizonyításához, hogy minden élt
felhasználtunk, tekintsük
T
egy fel nem használt és
x
0
-hoz legközelebb eső élét.
- 11. feladat F M
Az Euler-vonalat tekinthetjük úgy, mint
x
0
-ból egy meghatározott élen induló út.
Mutassuk meg, hogy minden Euler-vonal előáll az
5.10-ben adott algoritmus szerint valamely feszítő
fenyővel.
- 12. feladat F M
Nevezzünk egy pontot „jó”-nak, ha minden hozzá
illeszkedő élen már mindkét irányban áthaladtunk.
Nézzük az első „rossz” pontot, mellyel sétánk során
találkozunk.
- 13. feladat F M
Bizonyítsuk, majd alkalmazzuk azt az állítást,
hogy egy páros fokú és izolált pontot nem tartalmazó
gráf él-diszjunkt körök uniójából áll.
- 14. feladat F M
(a) Használjuk 5.13-at és
5.6-ot. (b) Vegyünk egy
új pontot és kössük össze minden páratlan fokú
ponttal.
- 15. feladat F M
Alkalmazzunk indukciót az élek számára.
- 16. feladat F M
Alkalmazzunk indukciót az élek számára; vegyük
észre, hogy ha
G
1
feszítő részgráf páros fokszámokkal és
K
egy kör, akkor (
V
(
G
)
,
E
(
G
1
)
△
E
(
K
)
) szintén feszítő részgráf páros
fokszámokkal (röviden „jó” részgráf).
- 17. feladat F M
(a) Alkalmazzunk indukciót
n
-re. Hagyjunk el egy páratlan fokú
pontot és változtassuk a gráfot a komplementerére a
szomszédai halmazán belül. (b) Vegyünk fel egy új
pontot és kössük össze
V
(
G
)
szomszédaival. (c) Vegyünk fel egy új
pontot és kössük össze minden páros fokú
ponttal.
- 18. feladat F M
(a) Vegyük a teljessé tett
V
(
G
)
gráf minden
r
-elemű párosítását, és szitáljuk ki
azokat, melyeknek tartalmaznak
G
-beli élt. (b) (a)-ból. (c) Az
1-faktorok száma ugyanolyan paritású, mint a
csúcsmátrix determinánsa.
- 19. feladat F M
Indokoljunk a fentihez hasonlóan. Irányítatlan
gráfokra az állítás akkor igaz, ha
|
V
(
G
)
|
>
3
.
- 20. feladat F M
Mutassuk meg, hogy egy él irányítását megfordítva
a Hamilton-utak számának paritása nem változik.
- 21. feladat F M
Vegyük azon
(
F
1
,
F
2
)
1-faktor párokat, melyekre
F
1
∩
F
2
=
∅
,
e
∈
F
1
. Mutassuk meg, hogy az ilyen párok
száma páros, és használjuk fel ezt a tényt.
- 22. feladat F M
Redukáljuk a gráfot a 14. ábrának megfelelően, és
különböztessük meg az éleken különböző irányban átmenő
Hamilton köröket.
- 23. feladat F M
Legyen
F
a
G
egy feszítő fája. Mutassuk meg, hogy
G
∗
azon élei, melyek nem feleltethetők
meg
F
éleinek,
G
∗
egy feszítő fáját alkotják.
- 24. feladat F M
Használjuk az előző bizonyítást.
- 25. feladat F M
Minden lap határán legalább három él van.
- 26. feladat F M
Hagyjuk el egy lap határén lévő éleket.
- 27. feladat F M
(a) Használjuk a lapok egy 2-színezését. (b)
Számoljuk meg a piros-kék sarkokat az Euler formula
segítségével.
- 28. feladat F M
(a) Tekintsük a lapok egy 2-színezését. (b)
Vegyünk fel egy új pontot az ötszögön kívül és kössük
össze a páratlan fokú pontokkal.
- 29. feladat F M
Számoljuk meg azon éleket, melyek piros pontot
kékkel kötnek össze.
- 30. feladat F M
Egy
x
pontot akkor színezzünk pirosra, ha
x
∈
V
1
, és
V
1
tartalmaz egy
(
x
,
a
)
utat; kékre, ha
x
∈
V
2
, és
V
2
tartalmaz egy
(
x
,
b
)
utat; különben zöldre. Mutassuk meg,
hogy nincsen mind a három színt tartalmazó
háromszög.
- 31. feladat F M
Csak (f) bizonyítása nehezebb valamelyest.
Vegyük
V
egy
{
v
1
,
…
,
v
k
,
v
k
+
1
,
…
,
v
n
}
bázisát, ahol
〈
v
1
,
…
,
v
k
〉
=
M
és tekintsük a következőképpen
definiált
A
transzformációt:
- 32. feladat F M
(a) Bizonyítsuk, majd alkalmazzuk, hogy
〈
M
∪
M
⊥
〉
=
(
M
∩
M
⊥
)
⊥
. (b) Ha
a
az
A
főátlója alkotta oszlopvektor, akkor
v
T
A
v
=
a
T
v
minden
G
F
(
2
)
feletti
v
vektorra teljesül.
- 33. feladat F M
(a) A csillagok a vágások alterét generálják, az
ortogonális altér azon élek halmazaiból áll, melyek egy
páros fokú részgráfot alkotnak. (b) Használjuk
4.9-et.
- 34. feladat F M
Mutassuk meg, hogy minden
C
kör a
C
által tartalmazott lapok
összege.
- 35. feladat F M
(a) Mutassuk meg, hogy
∑
i
∈
I
∪
J
C
i
⊆
K
. (b) Tekintsünk egy
I
halmazt, melyre
K
=
∑
i
∈
I
C
i
kör,
|
I
|
≥
2
és
|
I
|
minimális. (c) Használjuk (b)-t és
indukciót
f
-re. (d) (c) és 5.34 miatt.
- 36. feladat F M
Használjuk a MacLane feltételt.
- 37. feladat F M
(a) Feltéve, hogy
G
=
G
1
∪
G
2
,
V
(
G
1
)
∩
V
(
G
2
)
=
{
x
,
y
}
, húzzuk össze
G
1
−
x
-et és
G
2
−
x
-t. (b) Tekintsünk egy maximális utat.
(c) Hagyjuk el a körből a húrt, a síkon rajzoljuk le a
maradékot és válasszuk meg a kört úgy, hogy a
belsejében lévő területek száma maximális. Bizonyítsuk
be, hogy a gráfnak csak a körön kívül lehet húrja. (d)
(c) és 5.25b miatt azonnal adódik.
- 38. feladat F M
Elég a háromszögelt síkgráfokkal foglalkozni.
(Bizonyítandó!) Keressünk olyan
e
élt, melyet pontosan két háromszög
tartalmaz. Húzzuk össze
e
-t, és használjunk indukciót.