Jump to navigation

Belépés
  • Elfelejtettem a jelszavam
Regisztráció
 
  • Hogyan működik a mateking?
  • Mire jó a matek?
  • Matek érettségi
  • Képletgyűjtemény
  • Feladatgyűjtemény
  • Rólunk
  • Matek 5. osztály próbaüzem
  • Matek 6. osztály próbaüzem
  • Matek 7. osztály próbaüzem
  • Matek 8. osztály próbaüzem
  • Matek 9. osztály
  • Matek 10. osztály
  • Matek 11. osztály
  • Matek 12. osztály
  • Középiskolai matek (teljes)
  • Középszintű matek érettségi
  • Emelt szintű matek érettségi
  • Egyetemi matek alapozó
Összes egyetemi tantárgy
Legnépszerűbb tantárgyak:
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Valószínűségszámítás
  • Lineáris algebra
  • Diszkrét matematika
  • Statisztika

mateking

Login
 

Számítástudomány alapjai

Kategóriák
  • Kombinatorika
  • Gráfelméleti alapok
  • Gráfok bejárása és gráfalgoritmusok
  • Gráfok izomorfiája és síkbarajzolhatósága
  • Irányított gráfok, gráfalgoritmusok irányított gráfokban
  • Menger tételei, többszörös összefüggőség
  • CPM és PERT algoritmus
  • Páros gráfok, párosítások
  • Kromatikus szám, klikk, perfekt gráfok
  • Gráfparaméterek, párosítások
  • Maximális folyam, Ford-Fulkerson-algoritmus
  • Mátrixok és vektorok
  • Vektorterek, független és összefüggő vektorok
  • Lineáris egyenletrendszerek, mátrixok rangja és inverze
  • Determináns, sajátérték, sajátvektor
  • Lineáris leképezések
  • Oszthatóság
  • Euklideszi algoritmus & Diofantoszi egyenletek
  • Kongruenciák

Gráfparaméterek, párosítások

  • Epizódok
  • Feladatok
  • Képletek
01
 
Független és lefogó ponthalmaz, Gallai első tétele
02
 
Független és lefogó élhalmaz, Gallai második tétele
03
 
Gráfparaméterek
04
 
Párosítás, maximális párosítás, teljes párosítás
05
 
Teljes párosítás, Tutte-tétel
06
 
Különböző trükkök a gráfparaméterek kiszámolására
07
 
Furmányos gráfparaméteres egyenlőtlenségek
08
 
FELADAT | Gráfparaméterek
10
 
FELADAT | Gráfparaméterek
11
 
FELADAT | Gráfparaméterek
12
 
FELADAT | Gráfparaméterek
13
 
FELADAT | Gráfparaméterek
14
 
FELADAT | Gráfparaméterek

Független ponthalmaz

A független ponthalmaz precíz definíciójára mindjárt kettő is van.

Íme az egyik:

Egy $G$ gráfban független csúcshalmaznak nevezzük a csúcsoknak az $A \subset V(G)$ részhalmazát, ha nincs olyan él, amelynek mindkét végpontja $A$-ban van.

És itt jön a másik:

Egy $G$ gráfban független csúcshalmaznak nevezzük a csúcsoknak az $A \subset V(G)$ részhalmazát, ha az $A$ által feszített részgráf nem tartalmaz élt.

Egy $G$ gráfban a független csúcsok maximális számát $\alpha(G)$-vel jelöljük.

Megnézem a kapcsolódó epizódot

Gallai első tétele

Ha vesszük egy gráfban a maximális számú független pontokat és a minimális számú lefogó pontokat, akkor épp megkapjuk a gráf összes pontját.

Ezt hívjuk első Gallai tételnek:

\( \tau(G) + \alpha(G) = n \)

Megnézem a kapcsolódó epizódot

Lefogó ponthalmaz

Egy $G$ gráfban a $T \subset V(G)$ ponthalmaz lefogó ponthalmaz, ha $G$ minden élének legalább az egyik végpontja $T$-ben van.

Egy gráfban a minimális méretű lefogó ponthalmaz elemszámát $\tau(G)$-vel jelöljük.

A maximális lefogó ponthalmaz pedig a gráf összes csúcsa, és elemszáma éppen $ \mid V(G) \mid = n $.

Megnézem a kapcsolódó epizódot

Független élhalmaz

Egy $G$ gráf éleinek $M$ részhalmaza független élhalmaz, ha $M$ semelyik két elemének nincs közös végpontja.

Egy gráf független éleinek maximális számát $\nu(G)$-vel jelöljük.

Megnézem a kapcsolódó epizódot

Gallai második tétele

Ha vesszük egy gráfban a minimális számú lefogó éleket, és a maximális számú független éleket, akkor a gráf minden pontjához pontosan egy él fog tartozni.

Ez Gallai második tétele:

Ha egy $n$ csúcsú gráf nem tartalmaz izolált pontot, akkor

\( \rho(G) + \nu(G) = n \)

Megnézem a kapcsolódó epizódot

Lefogó élhalmaz

Egy $G$ gráf éleinek $R$ részhalmaza lefogó élhalmaz, ha a gráf minden csúcsa valamelyik $R$-beli él végpontja.

Egy $G$ gráfban a lefogó élek minimális számát $\rho(G)$-vel jelöljük.

Megnézem a kapcsolódó epizódot

Gráfparaméterek közti összefüggések

\( \alpha(G) \leq \rho(G) \quad \nu(G) \leq \tau(G) \)

Megnézem a kapcsolódó epizódot

Párosítás

Egy $G$ gráfban az $E(G)$ élhalmaznak egy $M$ részhalmazát párosításnak nevezzük, ha $M$ semelyik két elemének nincs közös végpontja.

Megnézem a kapcsolódó epizódot

Párosítás javító útja

Egy $G$ gráfban az $e_1, e_2, e_3, \dots , e_n$ élsorozat az $M$ párosítás javító útja, ha

1) a megadott élsorozat egy páratlan hosszú út $G$-ben

2) az élek felváltva elemi $M$-nek:

$ e_{2k} \in M$ és $e_{2k+1} \notin M $

3) az út kezdő és végpontja nem illeszkedik semelyik $M$-beli élre sem

Megnézem a kapcsolódó epizódot

Teljes párosítás

Azokat a párosításokat nevezzük teljes párosításoknak, ami a gráf összes csúcsát lefedi.

Megnézem a kapcsolódó epizódot

Tétel páros gráfokra

Egy $G$ gráf akkor és csak akkor páros, ha minden $G$-ben szereplő kör páros hosszúságú.

Megnézem a kapcsolódó epizódot

Tutte-tétel

Egy gráfban akkor és csakis akkor létezik teljes párosítás, ha bárhogyan hagyunk el a gráfból néhány pontot, a megmaradt gráfban a páratlan komponensek száma nem több az elhagyott pontok számánál.

Megnézem a kapcsolódó epizódot

1.

a) Egy gráfban $2n$ darab pont van, és minden pont foka legalább $n$. Legalább hány elemű egy lefogó élhalmaz a gráfban?

b) Egy 1001 pontú $G$ egyszerű gráfban $\tau{(G)}=1000$. Bizonyítsuk be, hogy $G$ teljes gráf.

Megnézem, hogyan kell megoldani

2.

a) Bizonyítsuk be, hogy minden $G$ egyszerű gráfra:

\( \chi{(G)} \cdot \alpha{(G)} \geq n \)

b) Bizonyítsuk be, hogy minden $G$ egyszerű gráfra:

\( 2\nu{(G)} \geq \tau{(G)} \)

c) Vajon minden $G$ egyszerű gráfban teljesül-e, hogy

\( \mid E(G) \mid \leq \Delta(G) \cdot \tau{(G)} \)

d) Bizonyítsuk be, hogy minden $G$ egyszerű gráfra:

\( \alpha{(G)} \left( \Delta(G)+1 \right)  \geq n \)

e) Bizonyítsuk be, hogy bármely $G$ egyszerű gráfban:

\( \chi{(G)} + \alpha{(G)} \leq n +1  \)

f) Bizonyítsuk be, hogy bármely $G$ egyszerű gráfban:

\( \begin{pmatrix} \chi{(G)} \\ 2 \end{pmatrix} \leq \mid E(G) \mid \)

Megnézem, hogyan kell megoldani

3.

A $G$ gráf csúcshalmaza $V(G)=\{1,2, \dots, 30 \}$. Az $x,y \in V(G)$ csúcsok akkor legyenek szomszédosak $G$-ben, ha $x \neq y$ és $x \cdot y$ osztható 6-tal. Határozzuk meg $\nu(G)$ értékét!

Megnézem, hogyan kell megoldani

4.

Egy $G$ gráf csúcsai legyenek a 100-nál nem nagyobb pozitív egészek. Két különböző csúcs pontosan akkor szomszédos $G$-ben, ha a megfelelő egészek relatív prímek. Határozzuk meg a gráfparamétereket!

Megnézem, hogyan kell megoldani

5.

Egy $G$ gráf csúcsai legyenek a 100-nál nem nagyobb pozitív egészek. Két különböző csúcs pontosan akkor szomszédos $G$-ben, ha a hozzájuk tartozó számok szorzata osztható 4-gyel. Határozzuk meg $\alpha{(G)}$ és $\rho{(G)}$ értékeit!

Megnézem, hogyan kell megoldani

6.

Egy 1000 csúcsú gráfban $\tau{(G)}=400$. Igazoljuk, hogy $G$-ben nincs teljes párosítás.

Megnézem, hogyan kell megoldani

A témakör tartalma


Független és lefogó ponthalmaz, Gallai első tétele

Független és lefogó élhalmaz, Gallai második tétele

Gráfparaméterek

Párosítás, maximális párosítás, teljes párosítás

Teljes párosítás, Tutte-tétel

Különböző trükkök a gráfparaméterek kiszámolására

Furmányos gráfparaméteres egyenlőtlenségek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

FELADAT | Gráfparaméterek

Kapcsolatfelvétel
  • Segítségnyújtás
  • Hibabejelentés
  • Kapcsolatfelvétel
  • Mateking torrent bejelentés
Rólunk
  • A projektről
  • Médiamegjelenések
  • Legyen élmény a matek
  • Mire jó a matek?
Tartalomjegyzék
  • Középiskolai matek
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Lineáris algebra
  • Valószínűségszámítás
  • Diszkrét matematika
  • Statisztika
  • További tantárgyak
  • Egyetemi tematikák
  • Matek érettségi
GYIK Általános szerződési feltételek Adatkezelési tájékoztató Felhasználás oktatási célra

Cookie-használat módosítása

© Minden jog fenntartva!

Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!

barion
macroweb
  • Tantárgyaim