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
 

Diszkrét matematika

Kategóriák
  • Kombinatorika
  • Halmazok, rendezett párok, leképezések
  • Matematikai logika, ítéletkalkulus
  • Gráfelméleti alapok
  • Gráfok izomorfiája és síkbarajzolhatósága
  • Gráfok bejárása és gráfalgoritmusok
  • Kromatikus szám, klikk, perfekt gráfok
  • Gráfparaméterek, párosítások
  • Hálózatok
  • Irányított gráfok, gráfalgoritmusok irányított gráfokban
  • Menger tételei, többszörös összefüggőség
  • Páros gráfok, párosítások
  • Teljes indukció
  • Oszthatóság
  • Euklideszi algoritmus & Diofantoszi egyenletek
  • Kongruenciák
  • Mátrixok
  • Lineáris egyenletrendszerek
  • Determinánsok
  • Komplex számok
  • Polinomok
  • Interpolációs polinomok
  • Csoportok, gyűrűk, testek

Kromatikus szám, klikk, perfekt gráfok

  • Epizódok
  • Feladatok
  • Képletek
01
 
Gráfok színezése, kromatikus szám
02
 
Klikk, klikkszám, kromatikus szám
03
 
Feszített részgráf, perfekt gráf
04
 
Mohó színezés, becslés a kromatikus számra
05
 
Gráfszínezés feladatok, Brooks-tétel
06
 
Élkromatikus szám, Vizing-tétel
07
 
Néhány remek gráf kromatikus száma és élkromatikus száma
08
 
Intervallumgráfok
09
 
Páros gráfok kromatikus száma és élkromatikus száma
10
 
A Mycielski-konstrukció
11
 
FELADAT | Kromatikus szám, élkromatikus szám
12
 
FELADAT | Kromatikus szám, élkromatikus szám
13
 
FELADAT | Kromatikus szám, élkromatikus szám
14
 
FELADAT | Kromatikus szám, élkromatikus szám
15
 
FELADAT | Kromatikus szám, élkromatikus szám
16
 
FELADAT | Kromatikus szám, élkromatikus szám
17
 
FELADAT | Kromatikus szám, élkromatikus szám

Kromatikus szám

A legkevesebb színt, amivel egy gráf csúcsait kiszinezhetjük úgy, hogy a szomszédos csúcsok ne legyenek egyforma színűek, a gráf kromatikus számának nevezzük.

Jele: $\chi (G)$.

Megnézem a kapcsolódó epizódot

Klikk

Egy $G$ egyszerű gráfban klikknek nevezzük azokat a részgráfokat, amelyek teljes gráfok.

Megnézem a kapcsolódó epizódot

Klikkszám

Egy gráf klikkszáma a gráfban található maximális klikk elemszáma.

A $G$ gráf klikkszámát $\omega (G)$-vel jelöljük.

 

Minden gráfban a klikkszám alsó becslés a kromatikus számra:

\( \omega (G) \leq \chi (G) \)

Megnézem a kapcsolódó epizódot

Feszített részgráf

A $G$ gráfban a $G'$ részgráf feszített részgráf, ha bármely két csúcs a $G'$ gráfban pontosan akkor szomszédos, ha $G$-ben is szomszédos.

Megnézem a kapcsolódó epizódot

Perfekt gráf

Ha egy $G$ gráf minden $G'$ feszített részgráfjára igaz, hogy

\( \omega (G') = \chi (G') \)

akkor a $G$ gráfot perfekt gráfnak nevezzük.

 

Ha egy gráf perfekt, akkor a kromatikus száma egyenlő a klikkszámával. Az állítás fordítva nem igaz, abból, hogy $\omega (G') = \chi (G')$ még nem következik, hogy a gráf perfekt.

Megnézem a kapcsolódó epizódot

Kromatikus szám alsó és felső becslése

\( \omega(G) \leq \chi(G) \leq \Delta(G) + 1 \)

ahol $\omega(G)$ a gráf klikkszáma, $\chi(G)$ a kromatikus száma és $\Delta(G)$ a maximális fokszáma.

Megnézem a kapcsolódó epizódot

Mohó színezés

A mohó színezés egy algoritmus a gráfok színezésére.

Lényege, hogy sorba rakjuk a gráf csúcsait, és elkezdjük színezni úgy, hogy minden csúcs színezéséhez a lehető legkisebb sorszámú színt használjuk. Ezt addig folytatjuk, amíg az összes csúcs ki nem lesz színezve, és így elhasználunk legfeljebb $\Delta(G)+1$ darab színt.

Megnézem a kapcsolódó epizódot

Brooks-tétel

Ha $G$ nem teljes gráf, vagy páratlan csúcsú kör, akkor

\( \chi(G) \leq \Delta(G) \)

Megnézem a kapcsolódó epizódot

Élkromatikus szám

Egy $G$ gráfban azt a legkisebb számot, amire a gráfnak már van jó élszínezése, a $G$ gráf élkromatikus számának nevezzük.

Jele: $\chi_e$

Megnézem a kapcsolódó epizódot

Vizing-tétel

A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést:

\( \Delta(G) \leq \chi_e(G) \leq \Delta(G) + 1 \)

Vagyis a $G$ egyszerű gráfok két osztályba sorolhatók:

Első osztály: $\chi_e(G) = \Delta(G)$

Második osztály: $\chi_e(G) = \Delta(G)+1 $

Megnézem a kapcsolódó epizódot

Intervallumgráfok

Az intervallumgráf egy olyan gráf, melynek csúcsai megfeleltethetőek a valós számok egy-egy intervallumának, és két csúcs között akkor vezet él, ha a nekik megfeleltethető két intervallum metszete nem üres.

Az intervallumgráfok mindig perfekt gráfok.

Megnézem a kapcsolódó epizódot

Páros gráf

Egy $G$ gráfot páros gráfnak nevezünk, ha csúcsainak a $V(G)$ halmaza felbontható az $A$ és $B$ diszjunkt részhalmazokra, úgy hogy $A$-n és $B$-n belül nem vezetnek élek.

A páros gráfok kromatikus száma 2, élkromatikus számukra pedig König Dénesnek van egy remek tétele:

Ha $G$ páros gráf, akkor $ \chi_e(G) = \Delta(G) $

Megnézem a kapcsolódó epizódot

Mycielski-gráfok

Jan Mycielski lengyel matematikust nyugtalanította az a kérdés, hogy léteznek-e olyan gráfok, amelyeknek a kromatikus száma nagyon nagy, de a klikkszáma csak 2.

Létrehozott egy konstrukciót, amivel olyan gráfokat lehet alkotni, amelyek klikkszáma 2, a kromatikus számuk pedig bármilyen nagy lehet. Ezeket a gráfokat Mycielski-gráfoknak nevezzük.

Megnézem a kapcsolódó epizódot

1.

a) Egy $G$ gráfban 1000 darab csúcstól eltekintve minden pont foka legfeljebb 999. Bizonyítsuk be, hogy a gráf kromatikus száma legfeljebb 1000.

b) Egy $G$ gráf csúcshalmaza legyen a $V(G)=\{1,2,3,\dots,30\}$ és két csúcs akkor legyen szomszédos, ha a különbségük legalább 6. Mekkora ennek a gráfnak a kromatikus száma?

Megnézem, hogyan kell megoldani

2.

Egy 1001 csúcsú gráf úgy keletkezik, hogy egy 1000 csúcsot tartalmazó kör minden pontját összekötjük az 1001-edik csúccsal. Mekkora ennek a gráfnak az élkromatikus száma?

Megnézem, hogyan kell megoldani

3.

a) Egy 2000 csúcsú G gráf két darab egyenként 1000 csúcsot tartalmazó körből készítettünk, úgy, hogy az egyik kör minden csúcsát összekötöttük a másik kör minden csúcsával.

Mekkora az így keletkező G gráf kromatikus száma és élkromatikus száma?

b) Számoljuk ki a Petersen gráf kromatikus számát.

c) Egy $G$ gráf csúcshalmaza legyen $V(G)=\{ 1,2,3,\dots, 30 \} $ és két csúcs akkor legyen szomszédos, ha a számok távolsága legalább 5. Mekkora ennek a gráfnak a kromatikus száma?

d) Egy másik gráf csúcshalmaza szintén a $V(G)=\{ 1,2,3,\dots, 30 \} $. A gráf $x,y \in V(G)$ csúcsai pontosan akkor legyenek szomszédosak, ha $ \mid x -y \mid = 4$ vagy $ \mid x - y \mid =6$. Határozzuk meg a gráf kromatikus számát.

Megnézem, hogyan kell megoldani

4.

a) A $G$ gráf csúcshalmaza legyen a $V(G)=\{ 1, 2, 3, \dots, 30 \}$. Az $x,y \in V(G)$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x -y \mid = 3$ vagy $\mid x -y \mid = 5$. Határozzuk meg a $G$ gráf $\chi{(G)}$ kromatikus számát és $\chi_e{(G)}$ élkromatikus számát.

b) Egy 20 csúcsú fában 11 csúcs foka 1 és a maradék 9 csúcs foka is azonos. Határozzuk meg a fa élkromatikus számát.

c) Egy 1000 csúcsú gráfot úgy kaptunk, hogy vettünk két 500 pontú utat, és az egyik út minden pontját összekötöttük a másik út minden pontjával. Mekkora az így kelektező gráfnak a kromatikus száma és az élkromatikus száma?

d) Egy 1001 csúcsú $G$ gráfot két körből, egy 500 pontú és egy 501 pontú körből készítünk úgy, hogy az egyik kör minden csúcsát összekötjük a másik kör minden csúcsával. Mekkora az így keletkező gráf kromatikus száma és élkromatikus száma?

Megnézem, hogyan kell megoldani

5.

Egy 1000 csúcsú teljes gráfból elhagyjuk egy Hamilton-kör éleit. Mekkora lesz az így kapott gráf kromatikus száma?

Megnézem, hogyan kell megoldani

6.

A $G$ gráf csúcshalmaza $V(G)=\{1,2,\dots,100\}$. Az $x,y \in V(G)$ csúcsok akkor legyenek szomszédosak $G$-ben, ha $x \neq y$ és $10 \mid x \cdot y$.

Határozzuk meg $G$ kromatikus számát.

Megnézem, hogyan kell megoldani

7.

Egy 8 csúcsú teljes gráfból töröljük egy 6 csúcsú kör éleit. Határozzuk meg a kapott gráf kromatikus számát.

Megnézem, hogyan kell megoldani

8.

Egy 100 csúcsú teljes gráfból töröljük egy 50 csúcsú kör éleit. Határozzuk meg a kapott gráf kromatikus számát.

Megnézem, hogyan kell megoldani

9.

A $G$ gráf csúcshalmaza $V(G)=\{1,2,\dots,1000\}$. Az $x,y \in V(G)$ csúcsok akkor legyenek szomszédosak $G$-ben, ha $x \neq y$ és $(x,y) \geq 10$. Határozzuk meg $G$ kromatikus számát.

Megnézem, hogyan kell megoldani

10.

Határozzuk meg egy 6 csúcsú kör komplementerének élkromatikus számát.

Megnézem, hogyan kell megoldani

A témakör tartalma

Itt mindent megtudhatsz a gráfok kromatikus számáról. Elmeséljük, mit is jelent a kromatikus szám pontosan, hogyan kell kiszámolni, mire kell figyelni. Megnézzük, hogy mi az a klikk, és mi köze van a klikknek a kromatikus számhoz. Gyorsan és egyszerűen megtudhatod, hogy mi az a klikk, és mit jelent egy gráf klikkszáma. Megnézzük, hogyan kell kiszámolni, mi a kapcsolat a klikkszám és a kromatikus szám között, és kiderül, hogy vannak olyan perfekt gráfok, ahol a klikkszám és a kromatikus szám megegyezik. Megtudod, mit jelent az, hogy feszített részgráf, mik azok a perfekt gráfok, hogyan lehet őket felismerni. Megnézzük a perfekt gráfok klikkszámát és kromatikus számát, és kiderül néhány nagyon izgalmas dolog. Megnézheted, mit jelent a gráfok mohó színezése, hogyan kell elkészíteni egy gráf mohó színezését, és ez alapján becslést adni a kromatikus számra. A kromatikus szám alsó és felső becslése, példák. Az is kiderül, hogy mi az a Brooks-tétel. Megnézheted, mi az élkromatikus szám, hogyan lehet meghatározni egy gráf élkromatikus számát. Kiderül, hogyan működik a Vizing-tétel, és hogyan használhatjuk az élkromatikus szám kiszámolására. Élszínezés feladatok, megoldással, gráfok élkromatikus száma és élszínezése. Elmeséljük, mik azok az intervallumgráfok, hogyan keletkeznek, és mi az értelmük. Megnézzük az intervallumgráfok tulajdonságait, és azt, hogyan lehet egy gráfról eldönteni, hogy intervallumgráf-e vagy sem. Intervallumgráf feladatok megoldással. Ráadásul azt is megnézzük, hogyan kell kiszámolni egy páros gráf élkromatikus számát és kromatikus számát. Feladatok páros gráfok kromatikus számaival kapcsolatban, König Dénes tétele. Végezetül pedig röviden és szuper-érthetően elmeséljük, mi az a Mycielski-konstrukció, mi köze van a gráfok színezéséhez, a kromatikus számhoz és a klikkszámhoz. Mycielski gráfok, Grötzsch gráf.



Gráfok színezése, kromatikus szám

Klikk, klikkszám, kromatikus szám

Feszített részgráf, perfekt gráf

Mohó színezés, becslés a kromatikus számra

Gráfszínezés feladatok, Brooks-tétel

Élkromatikus szám, Vizing-tétel

Néhány remek gráf kromatikus száma és élkromatikus száma

Intervallumgráfok

A Mycielski-konstrukció

Páros gráfok kromatikus száma és élkromatikus száma

FELADAT | Kromatikus szám, élkromatikus szám

FELADAT | Kromatikus szám, élkromatikus szám

FELADAT | Kromatikus szám, élkromatikus szám

FELADAT | Kromatikus szám, élkromatikus szám

FELADAT | Kromatikus szám, élkromatikus szám

FELADAT | Kromatikus szám, élkromatikus szám

FELADAT | Kromatikus szám, élkromatikus szám

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