Wikiszótár

gráftulajdonság

Magyar

Kiejtés

  • IPA: [ ˈɡraːftulɒjdonʃaːɡ]

Főnév

gráftulajdonság

  1. (matematika, gráfelmélet) 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 ( ): 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 ( ): 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   eleme 1, ha van él az   és   csúcs között, különben 0.
  • Incidenciamátrix: Az   eleme 1, ha az   csúcsot és   é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   vagy   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.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=gráftulajdonság&oldid=3479388”