- 1. feladat F M
Alkalmazzunk indukciót
|
V
(
G
)
|
-re egy pont elhagyásával.
- 2. feladat F M
A második állítás bizonyításához legyen
V
1
egy maximális teljes részgráf
pontjainak halmaza.
- 3. feladat F M
Használjunk szín-párokat
G
1
∪
G
2
színezéséhez.
- 4. feladat F M
Tekintsünk egy
α
színezést, melyben minden szín
legalább kétszer előfordul, és egy
β
színezést
χ
(
G
)
színnel úgy, hogy a két színezésnek a
lehető legtöbb közös szín-osztálya legyen.
- 5. feladat F M
Alkalmazzunk indukciót
k
-ra, és 9.2 megoldásában szereplőhöz
hasonló újraszínezést.
- 6. feladat F M
Segít, ha megválaszoljuk azt a kérdést, hogy
lehet-e
α
(
G
⊕
K
m
)
nagyobb
|
V
(
G
)
|
-nél.
- 7. feladat F M
(a) Ha adott
G
1
egy színezése, színezzük
G
1
×
G
2
egy pontját az első koordinátájának
megfelelően. (b) Vegyük észre, hogy
G
×
G
⊇
G
. (c) Ha
α
a
G
×
K
n
,
n
>
k
egy
k
-színezése, használjuk fel a tényt,
hogy minden
v
∈
V
(
G
)
-re valamely szín kétszer szerepel a
{
(
v
,
x
)
:
x
∈
V
(
K
n
)
}
halmazban. (d) A
G
×
K
n
egy
α
n
-színezéséhez mutassuk meg, hogy ha
{
α
(
v
,
x
)
:
x
∈
V
(
K
n
)
}
különbözőek, akkor
v
bármely
u
szomszédjára
{
α
(
u
,
x
)
:
x
∈
V
(
K
n
)
}
is különbözőek. (e) Hány
n
-színezése van a
K
n
m
=
K
n
×
…
×
K
n
︸
m
gráfnak?
- 8. feladat F M
(d)-hez vegyük észre, hogy ha 3-színezni akarunk
egy páratlan kört, de minden pontnál kizárunk egy
színt, úgy ez akkor és csak akkor lehetséges, ha a
kizárt szín nem minden pontnál ugyanaz. (e)-hez
tekintsük először azt az esetet, amikor egy kivételével
minden partíció megengedett.
- 9. feladat F M
Először bizonyítsuk ezt irányított körmentes
gráfokra; az általános esethez lásd 6.11
megoldását.
- 10. feladat F M
Akkor és csak akkor, ha minden körben ugyanannyi
élt irányítottunk a kör mentén mindkét irányba.
- 11. feladat F M
Ha
G
→
a
G
egy említett tulajdonsággal rendelkező
irányítása, akkor
G
egy sétájához definiáljuk annak
költségét úgy, hogy egyet nyerünk, ha egy élen a
megfelelő irányban haladunk (kezdőpontból a végpontba),
egyébként veszítünk
k
−
1
-et. Igazoljuk, majd használjuk a
következőket:
(a) az
a
-ból
b
-be érkező séták költsége alulról
korlátos,
(b) ha
a
és
b
szomszédosak, akkor az
(
x
0
,
a
)
-séták és
(
x
0
,
b
)
-séták minimális költsége különböző,
de a különbség legfeljebb
k
−
1
.
- 12. feladat F M
(a) Keressük
G
pontjainak egy olyan
(
x
0
,
…
,
x
n
−
1
)
elrendezését, melyben minden
x
i
szomszédos valamely
x
j
-vel (
j
<
i
); kezdjük
x
n
−
1
színezésével. (b) Mutassuk meg, hogy
az előző megoldásban használt sorozat választható úgy,
hogy
x
0
szomszédos legyen
x
n
−
1
-gyel és
C
(
x
0
)
≠
C
(
x
n
−
1
)
.
- 13. feladat F M
(a) Tekintsük
x
0
,
x
n
−
2
,
x
n
−
1
-et, melyekre
(
x
n
−
2
,
x
n
−
1
)
∉
E
(
G
)
,
(
x
0
,
x
n
−
1
)
∈
E
(
G
)
,
(
x
0
,
x
n
−
2
)
∈
E
(
G
)
. (b) Ha
G
=
G
1
∪
G
2
úgy, hogy
V
(
G
1
)
∩
V
(
G
2
)
=
{
x
1
,
x
2
}
,
|
V
(
G
i
)
|
≥
3
, tekintsük
G
1
+
(
x
1
,
x
2
)
-t és
G
2
+
(
x
1
,
x
2
)
-t.
- 14. feladat F M
(a) Azt kell belátnunk, hogy a
„nem-szomszédosság” ekvivalencia-reláció. (b) Ágyazzuk
be
G
-t egy ugyanezen halmazon értelmezett,
ugyanezen tulajdonsággal rendelkező maximális gráfba.
(c) Tekintsük azon színezések halmazát, melyek egy
adott
e
él végpontjait különbözően
színezik.
- 15. feladat F M
Legyen
K
k
+
1
a legkisebb teljes gráf
K
-ban; ekkor
K
az összes nem-
k
-színezhető gráfok osztálya lesz.
Annak bizonyításához, hogy ezek valóban
K
-beliek, tekintsünk egy rögzített
pontszámú, de maximális élszámú ellenpéldát, és
mutassuk meg, hogy a „nem-szomszédosság” a pontokon
ekvivalencia-reláció.
- 16. feladat F M
Használjuk fel az előző eredményt.
- 17. feladat F M
(a) Páratlan körök. (b)
K
n
,
n
′
minden 3-színezésében az egyik osztály
monokromatikus. (c)
K
n
,
n
′
minden 5-színezésében a két osztály
közül az egyik csak két színt kap.
- 18. feladat F M
χ
(
G
′
)
>
χ
(
G
)
igazolásához legyen
α
a
G
′
egy színezése
1
,
…
,
χ
(
G
)
és
α
(
y
)
=
1
színekkel. „Vetítsük le”
α
-t úgy, hogy
G
egy olyan színezését kapjuk, mely nem
használja az 1-es színt.
- 19. feladat F M
(a) Hogyan nézne ki
G
−
(
x
3
,
x
4
)
egy 3-színezése? (b) Az elégségesség
bizonyításához használjuk 9.8-at.
- 20. feladat F M
Minden
k
≥
3
esetén lehetséges.
- 21. feladat F M
Ha
k
−
1
él lefogja
G
-ben a
G
1
és
G
2
részeket, tekintsük ezek
k
-színezését és permutáljuk a színeket,
hogy a két színezés összeilljen.
- 22. feladat F M
Ha
G
kritikusan
(
k
+
1
)
-kromatikus és
G
=
G
1
∪
G
2
úgy, hogy
V
(
G
1
)
∩
V
(
G
2
)
=
{
x
,
y
}
, akkor vizsgáljuk azon gráfok
k
-színezhetőségét, melyeket
G
1
-ből és
G
2
-ből az
x
és
y
pontok összekötésével vagy
azonosításával kapunk.
- 23. feladat F M
Legyenek
G
1
,
…
,
G
N
a
G
−
S
komponensei. Tekintsük
S
-nek a
G
−
V
(
G
i
)
(
i
=
1
,
…
,
N
)
k
-színezései által indukált
partícióit.
- 24. feladat F M
G
−
(
x
,
y
)
minden
k
-színezésében az
x
és
y
pontok színe azonos. Ha ez az
i
szín, akkor bármely
j
-re az
i
és
j
színű pontok halmazának tartalmaznia
kell egy
(
x
,
y
)
-utat.
- 25. feladat F M
(a) Tekintsük
K
n
-t, mint egy szabályos
n
-szög élei és átlói által alkotott
gráfot. (b)
L
(
K
)
¯
n
egy színezésében egy szín-osztályának
megfelelő élek vagy csillagot, vagy háromszöget
alkotnak. (c)
L
(
K
→
n
)
egy színezését tekintve
K
→
n
bármely két
u
és
v
pontjához kell, hogy legyen olyan
szín, mely szerepel az
u
-t elhagyó élek között, de nem
szerepel a
v
-t elhagyó élek között.
- 26. feladat F M
(a) Feltéve, hogy adott
L
(
G
)
egy színezése, színezzük
G
minden pontját az őt elhagyó élek
színeinek halmazával. (b) Az (a)-ban adott korlát
javításához használjuk 13.20-at.
- 27. feladat F M
(a) Használjuk pl. 9.18-at. (b) Ha
G
k
-ra
χ
(
G
k
)
=
k
, és minden
x
pontját egy éllel összekötjük egy új
x
′
ponttal, akkor ezt a részt
n
-színezve az új pontok halmaza nem
lehet monokromatikus. (c) Vegyük egy tranzitív
turnament iterált élgráfját.
- 28. feladat F M
(a) Hagyjunk el egy intervallumot, melynek bal
végpontja a lehető leginkább balra esik. (b) Tekintsük
I
1
-et és
a
-t mint korábban, de most hagyjuk el a
rendszerből az összes
a
-t tartalmazó intervallumot. (c)
Feltehetjük, hogy
V
(
G
)
=
V
(
C
)
. Tekintsük a
I
1
-et és
a
-t, mint korábban.
- 29. feladat F M
(a) Tekintsük azon köröket, melyeket két olyan ív
alkot, melyek
v
∈
S
-t
u
∈
S
-hoz
G
−
S
különböző komponensében kötik. (b) Az
elégségesség ugyanúgy következik, mint 9.28c. A
szükségességhez alkalmazzuk az (a) részt és indukciót.
(c) Alkalmazzunk indukciót és (a)-t.
- 30. feladat F M
Ez ekvivalens azzal, hogy
α
(
G
)
=
ϱ
(
G
)
.
- 31. feladat F M
Mutassuk meg, hogy
- 32. feladat F M
(a) Heurisztikus megfogalmazásban
P
-t „szintekre” kell particionálni.
Tekintsük a legfelső pontokat „első szintnek”, a
következő legnagyobb pontokat „második szintnek”, stb.
b) Alkalmazzuk 8.4-et.
- 33. feladat F M
9.31 nem eredményez perfekt gráfot, még akkor
sem, ha
G
1
és
G
2
perfektek.
- 34. feladat F M
Egy
ω
(
G
)
-színezés egy szín-osztálya
ilyen.
- 35. feladat F M
Az előző feltételt elég
G
′
-re bizonyítani abban az esetben, ha
csak az egyik
G
x
tartalmaz egynél több pontot.
- 36. feladat F M
Tekintsük a
V
(
G
)
λ
-színezések által indukált
partícióját.
- 37. feladat F M
Számoljuk meg a
λ
-színezéseket a szitaformula
segítségével.
- 38. feladat F M
G
−
e
mely
λ
-színezései nem
λ
-színezései
G
-nek?
- 39. feladat F M
Körök esetén alkalmazzuk az előző
formulát.
- 40. feladat F M
Ha
G
több komponensből áll, ezeket
függetlenül színezhetjük. Ha több tagja van, ezeket
majdnem függetlenül színezhetjük.
- 41. feladat F M
Hagyjuk el azt az intervallumot, melynek jobb
végpontja a leginkább balra esik.
- 42. feladat F M
Használjuk 9.38-at.
- 43. feladat F M
Alkalmazzunk indukciót
|
E
(
G
)
|
-re, de most egy fából
kiindulva.
- 44. feladat F M
Alkalmazzuk a 9.36 megoldásában szereplő
formulát.
- 45. feladat F M
Általánosabban:
(
−
1
)
n
−
1
P
G
(
λ
)
>
0
λ
∈
(
0
,
1
)
-re összefüggő gráf esetén.
Bizonyítsuk be ezt a 9.43 megoldásában szereplőhöz
hasonló indukcióval.
- 46. feladat F M
(a) Mutassuk meg, hogy a 0 akkor és csak akkor
egyszeres gyök, ha
G
összefüggő, 1 akkor és csak akkor
egyszeres gyök, ha
G
2-szeresen összefüggő vagy
≅
K
2
. (b) Alkalmazzunk indukciót és
9.38-at.
- 47. feladat F M
(a) 9.38-ból triviális. (b) Minden ilyen lineáris
relációnak teljesülnie kell abban a három esetben,
amikor
V
(
G
)
=
V
(
F
)
. (c) Mutassuk meg, hogy ez a (sőt
bármely) lineáris reláció általánosan teljesül, ha
teljesül abban a három esetben, amikor
V
(
G
)
=
V
(
F
)
.
- 48. feladat F M
Tekintsük a
3
−
5
2
értéket.
- 49. feladat F M
(a) Mutassuk meg, hogy a reláció fennáll, ha
G
valamilyen nagyon egyszerű
trianguláció és vezessük vissza a problémát erre az
esetre a négyszöglapok átlóinak „felcserélésével”;
használjuk a következő azonosságot:
(b) Alkalmazzunk „visszafelé” indukciót,
elhagyva éleket egy triangulációból.
- 50. feladat F M
Mutassuk meg, hogy
G
-ben van legfeljebb 5 fokú
pont.
- 51. feladat F M
Ha a lapokat már kiszíneztük az 1, 2, 3, 4
színekkel, adjuk az
α
színt azoknak az éleknek, melyek
szomszédosak 1 és 2, vagy 3 és 4 színű lapokkal; a
β
színt azoknak az éleknek, melyek
szomszédosak 1 és 3, vagy 2 és 4 színű lapokkal; a
maradék éleket színezzük
γ
színnel. A megfordításhoz először
színezzük ki a síkgráf azon tartományait, melyeket az
élek egy 3-színezése után piros-zöld és piros-kék élek
alkotnak.
- 52. feladat F M
Ha az éleket kiszíneztük az 1, 2, 3 színekkel,
rendeljük a
+
1
számot azon pontokhoz, melyeknél 1, 2,
3 az óramutató járásának megfelelő sorrendje a hozzá
illeszkedő éleknek, és rendeljünk
−
1
-et a többi ponthoz. A megfordításhoz
tekintsük
L
(
G
)
-t és használjuk 5.4-et.
- 53. feladat F M
Használjunk két színt a Hamilton-körön kívül és
két színt ezen belül.
- 54. feladat F M
(a) Használjunk indukciót, elhagyva egy
legfeljebb 4 fokú pontot, a maradékot 4 színnel
színezve és úgy módosítva ezt a színezést, hogy az
elhagyott pont szomszédságában csak 3 szín szerepeljen.
(b) Azonosítsunk két nem-szomszédos pontot egy lap
határán és alkalmazzunk az (a) részhez hasonló
érvelést.
- 55. feladat F M
Feltehetjük, hogy
G
egy trianguláció. Tekintsük a duális
síkgráfjának,
G
∗
-nak egy 1-faktorát.
- 56. feladat F M
Az elégségességhez irányítsuk az éleket úgy, hogy
ha 1 egységnyi munka szükséges egy élen az adott
irányban való áthaladáshoz, akkor 0 (mod 3) egységnyi
munka szükséges minden lap körüljárásához.
- 57. feladat F M
Tegyük fel, hogy nincsen az
x
-tengellyel párhuzamos egyenesünk.
Ekkor színezzük a pontokat egyenként az ordinátájuknak
megfelelő sorrendben.