- 1. feladat Ö M
(a) Létezik-e gráf a következő fokszámokkal: 3, 3, 3, 3, 5, 6, 6, 6, 6, 6, 6?
(b) Létezik-e páros gráf a következő fokszámokkal: 3, 3, 3,
3, 3, 5, 6, 6, 6, 6, 6, 6, 6, 6?
(c) Létezik-e egyszerű gráf a következő fokszámokkal: 1, 1,
3, 3, 3, 3, 5, 6, 8, 9?
- 2. feladat Ö M
Mely számok fordulnak elő
k
-reguláris egyszerű gráf pontszámaként?
- 3. feladat Ö M
Egy gráf akkor és csak akkor páros, ha minden köre
páros. Igaz-e ez az állítás (irányított körökkel) irányított
gráfokra? És erősen összefüggő irányított gráfokra?
- 4. feladat Ö M
Egy
G
irányított gráf minden éléhez hozzárendelünk egy
v
(
e
)
értéket. Ez jelentheti az
e
-n adott irányban való végighaladáshoz szükséges
munkát. Az ellenkező irányban
−
v
(
e
)
munka szükséges. Keresünk egy „potenciált”, vagyis egy
V
(
G
)
-n értelmezett
p
(
x
)
függvényt, melyre ha
e
=
(
x
,
y
)
akkor
v
(
e
)
=
p
(
y
)
−
p
(
x
)
. Mutassuk meg, hogy ilyen akkor és csak akkor
létezik, ha bármely irányított kör mentén való végighaladáshoz a
szükséges összmunka 0.
- 5. feladat Ö M
Egy erősen összefüggő
G
gráf pontjai akkor és csak akkor színezhetők 2
színnel úgy, hogy minden pontot legalább egy irányított él köt
ellentétes színű ponthoz, ha
G
-ben van páros irányított kör.
- 6. feladat Ö M
Ha
G
gyengén összefüggő irányított gráf, melyben minden
x
-re
d
G
−
(
x
)
=
d
G
+
(
x
)
, akkor
G
-ben van Euler-vonal.
- 7. feladat Ö M
Definiáljuk a
G
k
,
n
gráfot (
k
≥
2
) a következő képpen: pontjai az
1
,
…
,
n
számokból alkotott
k
dimenziós vektorok; az
(
a
1
,
…
,
a
k
)
és
(
b
1
,
…
,
b
k
)
vektorok össze vannak kötve irányított éllel, ha
a
2
=
b
1
,
a
3
=
b
2
, …,
a
k
=
b
k
−
1
. Mutassuk meg, hogy
G
k
,
n
(a) Euler-gráf;
(b) Hamilton-gráf.
- 8. feladat Ö M
Mutassuk meg, hogy egy
2
k
hosszú irányított kör (
k
≥
2
) minden pontjához rendelhetünk 0-t vagy 1-et úgy,
hogy a kör minden
k
hosszú íve különböző 01-sorozatot adjon.
- 9. feladat Ö M
Ha
G
-ben van olyan pont, melynek kifoka legalább 3,
akkor az Euler-vonalak száma páros. (Két Euler-vonalat nem
tekintünk különbözőnek, ha az élek általunk megadott sorrendje csak
ciklikus permutációban különbözik egymástól.)
- 10. feladat Ö M
Legyen
G
egy irányított gráf, melyben minden pont kifoka
egyenlő a befokával. Legyen
T
egy inverz feszítő fenyő
x
0
gyökérrel.
x
0
-ból indulva bejárjuk
G
éleit a következő szabály szerint:
(
∗
) Minden
x
pontból még nem használt él mentén megyünk a
következő pontba (
x
-ből indulva).
T
éleit akkor használjuk, ha nincs más
lehetőségünk.
Mutassuk meg, hogy így
x
0
-ban akadunk el, és addigra egy Euler-vonalat
jártunk be.
- 11. feladat Ö M
Legyen
V
(
G
)
=
{
x
0
,
…
,
x
n
−
1
}
,
d
G
+
(
x
i
)
=
d
G
−
(
x
i
)
=
d
i
. Mutassuk meg, hogy
G
Euler-vonalainak száma
(
d
0
−
1
)
!
…
(
d
n
−
1
−
1
)
!
többszöröse.
- 12. feladat (Labirintus-feladat) Ö M
Egy
x
0
pontból indulva végighaladunk egy összefüggő
G
gráf élein a következő szabályok szerint:
(
∗
) Sohasem használjuk ugyanazt az élt kétszer
ugyanabban az irányban.
(
∗
∗
) Akárhányszor egy
x
≠
x
0
még nem érintett ponthoz érünk, megjelöljük azt az
élt, melyen
x
-be jutottunk. Csak akkor hagyjuk el
x
-et a megjelölt élen, ha máshogy nem lehet, vagyis
ha az összes többi élt már korábban használtuk.
Mutassuk meg, hogy
x
0
-ban akadunk el, és hogy addigra már minden élen
mindkét irányban áthaladtunk.
- 13. feladat Ö M
Ha a
G
gráfban minden fokszám páros, akkor
G
-t lehet úgy irányítani, hogy a kapott
G
→
irányított gráf minden pontjának kifoka egyenlő
befokával.
- 14. feladat Ö M
(a) Egy
G
gráfban akkor és csak akkor van Euler-vonal, ha
összefüggő és páros fokszámú.
(b) Ha egy összefüggő
G
gráfban
2
k
páratlan fokszámú pont van, akkor
k
-él-diszjunkt nyitott vonal (
k
≥
1
) uniója.
- 15. feladat Ö M
Ha egy síkgráfban van Euler-vonal, akkor a térkép
lerajzolható a ceruza felemelése nélkül úgy, hogy nem rajzoljuk át
újra és nem is keresztezzük a már megrajzolt vonalat (legfeljebb
érintjük).
- 16. feladat Ö M
Tekintsük egy összefüggő
G
gráf olyan
G
′
részgráfjait, melyek páros fokszámúak és
V
(
G
′
)
=
V
(
G
)
. Az ilyen részgráfok száma
2
m
−
n
+
1
(
m
=
|
E
(
G
)
|
,
n
=
|
V
(
G
)
|
).
- 17*. feladat Ö M
(a) Bármely
G
gráf pontjainak halmazán definiálható egy
V
1
,
V
2
partíció úgy, hogy
V
1
is és
V
2
is páros fokszámú részgráfot feszít ki.
(b) Bármely
G
gráfra
V
(
G
)
partícionálható két osztályba,
V
1
és
V
2
-be, úgy, hogy
V
1
páros fokszámú részgráfot feszít ki,
V
2
pedig páratlan fokszámút.
(c) Tételezzük fel, hogy egy gráf minden pontjában van egy
lámpa és egy gomb. Kezdetben minden lámpa ég. Egy gomb
megnyomásával ellenkezőjére változik a pontban lévő és a ponttal
szomszédos pontokban lévő lámpák állapota. Mutassuk meg, hogy
bizonyos gombok megnyomásával elérhető, hogy minden lámpa le legyen
oltva.
- 18. feladat Ö M
(a) Legyen
G
egy gráf, melyben jelölje
m
r
(
G
)
a
G
-ben lévő
r
-elemű párosítások számát. Fejezzük ki az
m
1
(
G
)
,
m
2
(
G
)
,
…
értékeket
|
V
(
G
)
|
=
n
és
m
1
(
G¯
)
,
m
2
(
G¯
)
, … segítségével.
(b) Ha
|
V
(
G
)
|
páros és
G¯
-ban páratlan számú párosítás van, akkor
G
-ben van 1-faktor.
(c)
G
-ben akkor és csak akkor van páros sok 1-faktor, ha van olyan nem üres
S
⊆
V
(
G
)
halmaz, hogy minden pont páros sok
S
-beli ponttal szomszédos (pl. Euler-gráfok esetén
S
=
V
).
- 19. feladat Ö M
Ha
G
egy egyszerű irányított gráf és
h
(
G
)
jelöli a
G
-beli Hamilton-utak számát, akkor
Igaz-e ez irányítatlan gráfokra?
- 20. feladat Ö M
Bármely turnamentben páratlan számú Hamilton-út van.
- 21. feladat Ö M
Egy 3-reguláris
G
gráf minden
e
élét páros számú Hamilton-kör tartalmazza.
- 22. feladat Ö M
Egy 3-reguláris, legalább 4 pontú páros gráfnak
páros számú Hamilton-köre van.
- 23. feladat Ö M
Legyen
G
egy összefüggő síkgráf,
G
∗
a duálisa. Mutassuk meg, hogy
G
-nek és
G
∗
-nak azonos számú feszítőfája van.
- 24. feladat (Euler formula) Ö M
Mutassuk meg, hogy ha
G
egy összefüggő síkgráf, akkor
m
−
n
+
2
lapja van, ahol
m
=
|
E
(
G
)
|
és
n
=
|
V
(
G
)
|
.
- 25. feladat Ö M
(a) Egy
n
pontú egyszerű síkbarajzolható gráfnak legfeljebb
3
n
−
6
éle van.
(b) Egy
n
pontú egyszerű háromszögmentes síkbarajzolható gráfnak legfeljebb
2
n
−
4
éle van.
- 26. feladat Ö M
Ha egy síkgráfnak páros fokszámai vannak, akkor
lapjai 2 színnel színezhetők oly módon, hogy él mentén érintkező
lapok színe különböző.
- 27. feladat Ö M
Legyen
G
egy egyszerű 4-reguláris síkgráf.
(a) Mutassuk meg, hogy
G
irányítható úgy, hogy minden pontnak két belépő és
két kimenő éle van, és ez a két pár elválasztja egymást az adott
beágyazásban.
(b) Bizonyítsuk be, hogy
G
éleit nem lehet 2 színnel színezni úgy, hogy
minden pont két piros és két kék élhez csatlakozik, és ez a két pár
elválasztja egymást az adott beágyazásban.
- 28. feladat Ö M
(a) Lehet-e síkgráfot rajzolni egy ötszög
belsejébe úgy, hogy a lapok háromszögek (természetesen a legkülső
kivételével) és minden pont foka páros?
(b) Tegyük fel, hogy egy ötszög belsejét egy síkgráffal
háromszögekre osztjuk úgy, hogy az ötszögön lévőket leszámítva
minden pont foka páros. Az ötszög mely pontjai lesznek páratlan
fokúak?
- 29. feladat Ö M
Legyen
G
egy síkgráf háromszög lapokkal. Tegyük fel, hogy
G
pontjai 3 színnel kiszínezhetők. Mutassuk meg,
hogy a mindhárom színt tartalmazó lapok száma páros.
- 30. feladat Ö M
Legyen
G
egy síkgráf, a külső
a
b
c
d
lap kivételével háromszög lapokkal. Legyen
V
(
G
)
=
V
1
∪
V
2
,
a
,
c
∈
V
1
,
b
,
d
∈
V
2
. Ekkor vagy
V
1
tartalmaz egy
(
a
,
c
)
utat, vagy
V
2
tartalmaz egy
(
b
,
d
)
utat.
- 31. feladat Ö M
Legyen
V
az
(
a
1
,
…
,
a
n
)
T
vektorok tere, ahol az
a
i
-k az
F
testből valók.
a
=
(
a
1
,
…
,
a
n
)
T
és
b
=
(
b
1
,
…
,
b
n
)
T
esetén a skalárszorzatukat
a
T
b
=
a
1
b
1
+
…
+
a
n
b
n
szerint definiáljuk. Továbbá legyen
M
a
V
egy altere és
A
a
V
egy lineáris transzformációja. Döntsük el, hogy a
következő állítások igazak-e[]:
(a) Ha
A
nem szinguláris, akkor a transzponáltja,
A
T
sem az.
(b) Általánosabban, ha
A
nem szinguláris, akkor
A
T
A
sem az.
(c) Még általánosabban,
Ker
A
T
A
=
Ker
A
.
(d)
M
∩
M
⊥
=
{
0
}
(ahol
M
⊥
az
M
-re ortogonális altér, tehát
M
⊥
=
{
a
:
a
T
b
=
0
minden
b
∈
M
-re
}
.
(e)
〈
M
∪
M
⊥
〉
=
V
(
〈
X
〉
jelöli az
X
által generált alteret).
(f)
dim
M
+
dim
M
⊥
=
n
.
(g)
M
⊥
⊥
=
M
.
- 32. feladat Ö M
(a) Legyen
V
a
G
F
2
fölötti
n
-dimenziós vektortér és
M
a
V
egy altere. Mutassuk meg, hogy
(b) Legyen
A
egy szimmetrikus 0-1 mátrix. Bizonyítsuk be, hogy
A
G
F
2
fölötti sor-tere tartalmazza
A
sorvektornak tekintett átlóját. Ennek
felhasználásával adjunk új bizonyítást 5.17-re.
- 33. feladat Ö M
Legyen
E
G
=
{
e
1
,
…
,
e
m
}
. Rendeljünk
E
G
minden részhalmazához egy 01-vektort, ahol a
j
-ik koordináta akkor és csak akkor 1, ha
e
j
benne van a megfelelő részhalmazban. Így
E
G
részhalmazait egy
G
F
2
fölötti
m
-dimenziós
V
G
vektortér elemeivel azonosítjuk.
(a) Határozzuk meg a csillagok által generált
U
G
alteret, valamint az ortogonális
W
G
alteret. Adjunk új bizonyítást 5.3,
5.16 és 5.17-re
ezen lineáris terek felhasználásával.
(b) Bizonyítsuk be, hogy az 5.17a felbontás akkor és csak
akkor egyértelmű, ha
G
-nek páratlan számú feszítő fája van.
- 34. feladat Ö M
Legyen
G
2-szeresen összefüggő síkgráf. Mutassuk meg, hogy
a véges lapok határvonalai a
W
G
tér egy bázisát alkotják.
- 35*. feladat Ö M
Legyen
G
egy gráf,
C
1
,
…
,
C
f
a
G
gráf körei, és tegyük fel, hogy
(1)
G
minden élét
C
1
,
…
,
C
f
közül legalább kettő tartalmazza;
(2)
C
1
,
…
,
C
f
körök
W
G
egy bázisát alkotják.
Mutassuk meg, hogy
(a) Ha
K
=
∑
i
∈
I
C
i
egy kör és
akkor
J
⊆
I
(
I
,
J
⊆
{
1
,
…
,
f
}
);
(b) vagy
G
minden tagja egyetlen kör, vagy van két
C
i
, mondjuk
C
1
és
C
2
, hogy
C
1
+
C
2
is kör;
(c)
G
síkgráf, és
C
1
,
…
,
C
f
lapok.
(d) (MacLane feltétel) Egy
G
gráf akkor és csak akkor síkbarajzolható, ha
W
G
-nek van olyan bázisa, hogy minden él legfeljebb
két eleméhez tartozik.
- 36*. feladat (Whitney feltétel) Ö M
Egy összefüggő
G
gráf akkor és csak akkor síkbarajzolható, ha
létezik egy másik
G
∗
gráf és egy olyan kölcsönösen egyértelmű
ϕ
leképezés
E
G
és
E
G
∗
közt, hogy minden
G
-beli
T
feszítőfára
ϕ
E
G
−
E
T
feszítőfát alkot
G
∗
-ben és viszont.
- 37*. feladat Ö M
Legyen
G
egy minimális nem-sík gráf (tehát
G
minden valódi részhalmaza síkgráf), melynek minden
fokszáma legalább 3. Ekkor
(a)
G
3-szorosan összefüggő,
(b)
G
tartalmaz egy kört húrral,
(c)
G
≅
K
5
vagy
K
3
,
3
,
(d) (Kuratowski feltétel) Egy gráf akkor és csak akkor
síkbarajzolható, ha nem tartalmazza
K
5
vagy
K
3
,
3
egy felosztását.
- 38*. feladat Ö M
Ha
G
egyszerű síkbarajzolható gráf, akkor
G
-t be lehet ágyazni a síkba úgy, hogy minden éle
egyenes szakasz legyen.