Bevezetés a számításelméletbe II.
3. gyakorlat 2002. február 28-március 1.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
Négy görög betű
- Bizonyítsuk be, hogy ha egy páros gráfban nincsen teljes párosítás,
akkor az
adjacencia (szomszédsági) mátrixra
. (Segítség: Használjuk a determináns
definícióját és mutassuk meg, hogy minden kifejtési tag 0.)
- Határozzuk meg az alábbi gráfokban az
és
értékeket.
- Mennyi
? (Azt a teljes páros gráfot jelöli
, melynek két pontosztálya
illetve
pontból áll.)
- Legyen
egy gráfban a maximális fokszám.
Bizonyítsuk be, hogy
.
- Igazoljuk, hogy egy hurokmentes
gráfban teljesül a
egyenlőtlenség!
- Egy egyszerű
gráfnak 1000 pontja van és,
bármely pontnak a foka legalább 6.
- Mutassuk meg, hogy
!
- HF Tudsz mutatni példát olyan a feladat feltételeit kielégítő
-re, ahol
?
- Határozzuk meg
-t és
-t az alábbi gráfokban!
- HF Legyen
egy
pontú gráf, mely egy
pontú
útból és egy
pontból áll, ami
minden pontjával össze van kötve. Mennyi
?
- HF Bizonyítsuk be, hogy egy fában legfeljebb egy teljes párosítás lehet!
- HF Egy
méretű, nem negatív elemeket tartalmazó mátrix bármely sorában lévő elemek összege 1, hasonlóan bármely oszlopban előforduló elemek összege is 1. Bizonyítsuk be, hogy a mátrix determinánsában szereplő
kifejtési tag nem lehet mind nulla.
- HF Legyen
egy maximális méretű független ponthalmaz az egyszerű
gráfban, és legyen
egy független ponthalmaz
-ben.
Bizonyítsuk be, hogy
!

-
Egy maximális
független ponthalmaz mérete;

-
Egy minimális lefogó ponthalmaz mérete;

-
Egy maximális független élhalmaz mérete;

-
Egy minimális lefogó élhalmaz mérete;

-
Maximális fokszám;
- :)
-
Kitartás, még jön két görög betű!!!