- 1. feladat F M
Mit jelent kombinatorikusan egy
sajátvektor?
- 2. feladat F M
(a) Használjuk azt a tényt, hogy az
(
1
,
…
,
1
)
vektor egy sajátvektor, és a
sajátvektorok páronként ortogonálisak. (b) Bizonyítsuk
be és használjuk az alábbi azonosságokat:
(c) A Petersen gráf megegyezik az
L
(
K
5
)
¯
gráffal.
- 3. feladat F M
Feltehetjük, hogy
V
(
T
)
=
{
x
1
,
…
,
x
n
}
,
e
=
(
x
k
,
x
k
+
1
)
(
1
≤
k
≤
n
−
1
)
, és hogy
T
−
e
=
T
1
∪
T
2
, ahol
V
(
T
1
)
=
{
x
1
,
…
,
x
k
}
és
V
(
T
2
)
=
{
x
k
+
1
,
…
,
x
n
}
. Tekintsük a
det
(
λ
I
−
A
)
kifejtését az első
k
sora szerint.
- 4. feladat F M
Végezzünk indukciót és használjuk az előző
gyakorlatot.
- 5. feladat F M
(a) következik 11.4 és
1.31-ből. Mind (a), mind
(b) következik indukcióval. (b) és (c) meg vannak oldva
lényegében 1.29-ben. (d)-hez, tekintsünk egy
y
sajátvektort, mely egy
λ
sajátértékhez tartozik, és invariáns a
fa automorfizmusai alatt, és vezessük le a
rekurziót, ahol
y
k
az
y
tetszőleges eleme, mely
k
távolságra van a gyökértől.
- 6. feladat F M
11.4 szerint, csak két olyan fát kell találnunk,
melyeknek ugyanannyi
k
-elemű párosításuk van minden
k
-ra. Keressük meg köztük azokat a
fákat, melyekben nincs 3 független él.
- 7. feladat F M
(a) Bizonyítsuk be, hogy
(b) Hogyan keletkezik az
A
G
1
⋅
G
2
adjacencia mátrix?
- 8. feladat F M
A
v
=
(
χ
(
τ
1
,
1
)
,
…
,
χ
(
τ
1
,
n
)
)
T
vektor egy sajátvektor.
- 9. feladat F M
A
Q
n
automorfizmus csoportja tartalmaz egy
kommutatív reguláris
(
Z
2
)
n
részcsoportot; használhatjuk 11.7a-t
is.
- 10. feladat F M
Ha
G
≅
H
, akkor a sajátértékeik
ugyanazok.
- 11. feladat F M
Vegyük észre, hogy a 0 akkor és csak akkor nem
sajátérték, ha
det
A
≠
0
.
- 12. feladat F M
Keressünk egy olyan sajátvektort, mely
a
-t rendel a 3-adfokú pontokhoz a fedő
részgráfokban, és
b
-t a többi ponthoz.
- 13. feladat F M
Használjuk fel, hogy
λ
1
=
max
|
v
|
=
1
v
T
A
G
v
.
- 14. feladat F M
(a) Használjuk az előző eredményt; az egyenlőség
esetének meghatározásához használjuk fel azt, hogy egy
összefüggő gráf adjacencia mátrixának van egy
(szigorúan) pozitív sajátvektora. (b) Használjuk fel,
hogy a sajátértékek összege 0, és a négyzeteik összege
2
m
. (c) Ágyazzuk be
G
-t egy teljes, gyökeres,
(
D
−
1
)
-adikus fába.
- 15. feladat F M
Használjuk a
A
L
(
G
)
=
B
T
B
−
2
I
formulát, ahol
B
pont-él incidencia mátrix:
- 16. feladat F M
A
G
tetszőleges
α
automorfizmusának megfelel egy
P
permutációs mátrix, melyre
A
G
P
=
P
A
G
. Használjuk ki azt is, hogy
A
=
T
−
1
L
T
, ahol
T
egy ortogonális mátrix és
L
egy diagonális mátrix, melynek az
átlójában vannak a sajátértékek.
- 17. feladat F M
Használjuk az előző eredményt annak
megmutatására, hogy
Γ
kommutatív és reguláris és alkalmazzuk
11.8-at, hogy kiszámítsuk a sajátértékeket.
- 18. feladat F M
Használjuk a sajátértékekre vonatkozó tételt: ha
A
egy szimmetrikus mátrix, melynek a
sajátértékei
λ
1
≥
λ
2
≥
…
≥
λ
n
és
B
szimmetrikus almátrixa
A
-nak, melynek sajátértékei
μ
1
≥
…
≥
μ
m
, akkor
λ
i
≥
μ
i
≥
λ
i
+
n
−
m
.
- 19. feladat F M
(a) Tegyük fel, hogy
A
G
w
=
−
λ
1
w
,
w
=
(
w
1
,
…
,
w
n
)
T
. Bizonyítsuk be, hogy
w
′
=
(
|
w
1
|
,
…
,
|
w
n
|
)
T
kielégíti a
−
w
T
A
G
w
=
w
′
T
A
G
w
′
egyenletet. (b) Tekintsünk egy
komponenst, amelynek a legkisebb sajátértéke
minimális.
- 20. feladat F M
Használjuk 11.13-at,
11.14-et és
indukciót.
- 21. feladat F M
(a) Mutassuk meg, hogy egy alkalmas bázisban,
A
-nak van egy
k
×
k
szimmetrikus
D
almátrixa, hogy a főátlóban 0-k
vannak, és úgy, hogy
λ
1
a
D
-nek egy sajátértéke. (b) 0 egy
sajátérték, melynek multiplicitása
n
−
k
.
- 22. feladat F M
Mutassuk meg, hogy minden
x
vektorra,
- 23. feladat F M
Tekintsünk egy vektort, mely konstans egy
maximális független halmazon, és annak a
komplementerén.
- 24. feladat F M
Írjuk fel
x
T
A
G
x
-et, mint
m
pozitív, és
m
negatív négyzet összegét.
- 25. feladat F M
Ha
f
(
λ
)
az a polinom, melynek a gyökei a
különböző sajátértékei
A
G
-nek, akkor
f
(
A
G
)
=
0
.
- 26. feladat F M
Mutassuk meg, hogy mindkét állítás ekvivalens
azzal, hogy „
A
G
minden sajátvektora sajátvektora
J
-nek”.
- 27. feladat F M
Számítsuk ki
A
L
2
-et.
- 28. feladat F M
(a)
A
G
kielégíti az
egyenletet. (b)
G
=
K
3
. (c) Általánosítsuk a
K
4
⊕
K
4
példáját.
- 29. feladat F M
(a) Tekintsünk egy
x
sajátvektort, mely a
λ
2
-höz tartozik, és azokat a tagokat
11.22-ben, melyek egy olyan út éleinek felelnek meg,
melyek az
x
legkisebb és legnagyobb elemét kötik
össze. (b) Tekintsük
A
G
2
−
d
I
-t.
- 30. feladat F M
Rendezzük a pontokat úgy, hogy
y
1
≤
y
2
≤
…
≤
y
n
legyen, és használjuk fel, hogy
i
<
j
esetén,
y
j
−
y
i
=
(
y
i
+
1
−
y
i
)
+
⋯
+
(
y
j
−
y
j
−
1
)
.
- 31. feladat F M
(a) Használjuk 11.22-t.
(b) Alkalmazzuk 11.30-at
y
i
=
(
max
{
x
i
−
x
¯
,
0
}
)
2
-nel, ahol
x
egy a
λ
2
-höz tartozó sajátvektor, és
x
¯
az
x
mediánsa.
- 32. feladat F M
(a) Használjuk 11.8-at, hogy kifejezzük
G
sajátértékeit. (b) Tekintsük minden
pontpár között a legrövidebb utakat, és az összes
képüket az automorfizmusok által.
- 33. feladat F M
(a) Fejezzük ki a kérdéses valószínűséget a
szitaformulával, és határozzuk meg a határértékét
n
→
∞
esetén (vö. 4.23 megoldásával). (b) Mi
annak a valószínűsége, hogy
M
1
p
élt tartalmaz
S
és
V
(
G
)
∖
S
között egy adott partícióra?
- 34. feladat F M
Jelölje
p
j
(
k
)
a
v
k
=
j
(
j
∈
V
(
G
)
) valószínűségét. Mutassuk meg, hogy
- 35. feladat F M
(a) Próbálkozzunk
p
i
(
0
)
=
d
(
i
)
∕
(
2
m
)
-mel. (b) A stacionárius eloszlás az
M
-nek egy sajátvektora. (c) Használjuk
11.34-et, és
11.19 egy verzióját.
- 36. feladat F M
Vegyük észre, hogy
P
(
v
j
=
y
|
v
i
=
x
)
éppen annak a valószínűsége, hogy egy
x
-ben induló véletlen séta az
y
-t a
(
j
−
i
)
-ik lépésben éri el.
- 37. feladat F M
(a) Használjuk 11.35(c)-t, és az
egyenlőséget. (b) Használjuk 11.36-ot, és a
egyenlőséget.
- 38. feladat F M
(a) Használjuk 11.37-et. (b) Keressünk, és
bizonyítsuk be, a 11.37 egy analogonját, az egy élen
való áthaladások számlálására.
- 39. feladat F M
Az
n
pontú út esetére, határozzuk meg az
elérési időt az
(
n
−
1
)
-edik pontból az
n
-edikbe először.
- 40. feladat F M
(a) Tekintsünk egy 2 hosszúságú utat. Ahhoz, hogy
egy reguláris példát kapjunk, válasszunk egy
u
elvágó pontot. (b) Létezik egy
természetes bijekció az
u
-ból
v
-be menő, és a
v
-ből
u
-ba menő séták között.
- 41. feladat F M
Egy
u
-ból
v
-be és vissza menő sétán, tekintsük az
első visszatérést
u
-ba.
- 42. feladat F M
(a) Keressünk egy bijekciót az
u
-ban induló,
v
-be, aztán
w
-be látogató körutak, és az
u
-ban induló,
w
-be, aztán
v
-be látogató körutak között. (b) Egy
rögzített
t
csúcsra, rendezzük a csúcsokat az
H
(
u
,
t
)
−
H
(
t
,
u
)
értékeknek megfelelően.
- 43. feladat F M
r
=
1
-re, használjuk 11.38(b)-t.
- 44. feladat F M
(a) Használjuk ki, hogy
i
≠
j
esetén,
(b) Mi a jobb oldala ennek az egyenletnek
i
=
j
-re? (c) Jelölje
p
i
j
(
t
)
azt a valószínűséget, hogy egy
i
-ben induló véletlen séta
j
-ben van
t
lépés után; jelölje
q
i
j
(
t
)
annak a valószínűségét, hogy egy
i
-ben induló véletlen séta eléri
j
-t a
t
-ik lépésben először. Mutassuk meg,
hogy
és fordítsuk le ezt a relációt a generátor
függvényeket használva.
- 45. feladat F M
(a) triviális, ha összeadjuk 11.44(c) eredményét.
(b)-hez használjuk fel 11.9 első megoldását.
- 46. feladat F M
(a)-hoz használjuk 11.44(c)-t. (b)-hez, vegyük
észre, hogy a
w
i
=
(
w
k
i
)
k
=
1
n
vektorok kölcsönösen ortogonális
egység vektorok.
- 47. feladat F M
(a) Keressük meg a lépések várható számát, míg
pontosan
i
pont marad meglátogatatlan. (b) Vö.
11.43.
- 48. feladat F M
(a) Bizonyítsuk be, hogy
μ
(
u
,
v
)
átlaga az összes
v
∈
V
(
G
)
∖
{
u
}
-ra,
n
∕
2
lesz. (b) Ha
α
v
a lépések száma, mielőtt meglátogatná
a séta
v
-t, akkor
b
az
α
v
-k mediánsának várható értéke.
- 49. feladat F M
11.48(b) szerint,
2
a
lépésben több, mint a felét láttuk az
összes csúcsoknak; további
2
a
lépésben láttuk a maradéknak több,
mint a felét, stb.
- 50. feladat F M
Használjuk 11.44(c) megoldási módszerét.
- 51. feladat F M
Használjuk 11.44(a)-t.
- 52. feladat F M
(a) triviális elemi valószínűségszámítási
módszerek felhasználásával. (b) következik a Kirchhoff
és Ohm törvényekből, (c) következik, ha tekintjük a
csúcspontokra ható erőket. (d) bizonyításához tekintsük
két olyan harmonikus függvény különbségét, mely az
adott tulajdonságokkal rendelkezik, és a csúcspontot,
ahol felveszi maximumát.
- 53. feladat F M
Mutassuk meg, és használjuk fel, hogy az
ellenállás
s
és
t
között
∑
u
∈
Γ
(
t
)
φ
s
t
(
u
)
−
1
. (b) Először viszonyítsuk
R
s
t
-t a 0-nál a szögre ható erőhöz. (c)
Számítsuk ki a Kirchhoff törvényből a pontok
feszültségeit, és használjuk 4.9-et.
- 54. feladat F M
Használjuk 11.53(b)-at.
- 55. feladat F M
(b)-hez, tekintsünk egy utat az
a
és
b
végpontokkal. (c)-hez, vegyük észre,
ha
(
a
,
b
)
-t használtuk, akkor elértük
t
-t.
- 56. feladat F M
(b) és (c)-hez, használjuk 11.44(c)-t és az
aritmetikai és harmonikus közepek közötti
egyenlőtlenséget.
- 57. feladat F M
(a) Mutassuk meg, hogy
π
(
u
,
v
)
független
v
-től, tekintve az első olyan lépést,
amikor meglátogattuk a
v
egy szomszédját. (b) Használjuk fel,
hogy létezik egy olyan séta, mely az
u
egy tetszőleges szomszédjában indul,
és az utolsó előtti meglátogatott csúcs
v
, és az utolsó
u
. (c) Használjuk 6.6(c)-t.
- 58. feladat F M
Legyen
P
(
S
,
u
)
az a valószínűség, hogy egy
u
-ban induló véletlen séta az
S
fát generálja, ahogy azt a problémában
leírtuk. Minden
(
u
,
v
)
∈
E
(
G
)
élre, jelölje
(
u
,
v
S
)
az első élt az
(
u
,
v
)
-úton
S
-ben. Bizonyítsuk be, hogy
- 59. feladat F M
Tekintsünk egy véletlen sorozatot.