gráftulajdonság

• IPA:

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.

• Ö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.

• 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 (${\displaystyle 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.

• 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.

• Krómaszám (${\displaystyle (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.

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

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

• 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.

• 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 ${\displaystyle K_{5}}$ vagy ${\displaystyle K_{3,3}}$ egy részgráfját.

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

• gráftulajdonság - Értelmező szótár (MEK)
• gráftulajdonság - Etimológiai szótár (UMIL)
• gráftulajdonság - Szótár.net (hu-hu)
• gráftulajdonság - DeepL (hu-de)
• gráftulajdonság - Яндекс (hu-ru)
• gráftulajdonság - Google (hu-en)
• gráftulajdonság - Helyesírási szótár (MTA)
• gráftulajdonság - Wikidata
• gráftulajdonság - Wikipédia (magyar)