Gráftulajdonság

1. Sablon:Label A gráfok tulajdonságai matematikai szempontból számos különböző kategóriába sorolhatók, például struktúrájuk, összefüggőségük, színezhetőségük vagy más specifikus jellemzőik alapján. Az alábbiakban a legfontosabb gráftulajdonságokat foglalom össze.

Gráftulajdonságok

1. Összefüggőség

• Összefüggő gráf: Ha a gráf bármely két csúcsa között létezik út.
• Erősen összefüggő (irányított gráf esetén): Ha bármely két csúcs között irányított út létezik.
• Komponensek száma: Az összefüggő részgráfok száma.

2. Gráftípusok

• Egyszerű gráf: Nincs párhuzamos él vagy hurokél.
• Irányított gráf (digráf): Az élek irányítottak.
• Teljes gráf ($K_n$): Minden csúcs összeköttetésben áll minden más csúccsal.
• Részgráf: Egy gráf, amely a kiindulási gráf csúcsainak és éleinek részhalmazából áll.

3. Fokszám

• Fokszám (degree): Egy csúcsból kiinduló vagy oda beérkező élek száma.
• Maximális/minimális fokszám: A gráfban a legnagyobb/legkisebb fokszámú csúcs értéke.

4. Színezhetőség

• Krómaszám ($(G)$): Az a minimális szín, amellyel a gráf csúcsai úgy színezhetők, hogy két szomszédos csúcs különböző színt kapjon.
• Élszínezés: Az élek színezése úgy, hogy egy csúcshoz tartozó élek különböző színt kapjanak.

5. Fa és erdő

• Fa: Olyan összefüggő gráf, amelyben nincs kör.
• Erdő: Körmentes, nem feltétlenül összefüggő gráf.

6. Gráfmátrixok

• Szomszédsági mátrix: Az $A[i][j]$ eleme 1, ha van él az $i$ és $j$ csúcs között, különben 0.
• Incidenciamátrix: Az $B[i][j]$ eleme 1, ha az $i$ csúcsot és $j$ élt összeköti, különben 0.

7. Merevség és Laman-gráf

• Egy gráf merev, ha síkba rajzolva a csúcsok pozícióját az élek mereven rögzítik.
• A Laman-gráfok merevséget jellemző speciális gráfok.

8. Síkbeliség

• Síkbeli gráf: A gráf úgy rajzolható le, hogy élei nem metszik egymást.
• Kuratowski-tétel: Egy gráf nem síkbeli, ha tartalmazza $K_5$ vagy $K_{3,3}$ egy részgráfját.

9. Gráfizomorfizmus

• Két gráf izomorf, ha létezik közöttük olyan bijekció, amely megőrzi a csúcsok és élek kapcsolatait.