irányítatlan gráf

Magyar

Kiejtés

IPA: [ ˈiraːɲiːtɒtlɒŋɡraːf]

Főnév

(matematika, gráfelmélet) Az összefüggő gráf a gráfelmélet egy alapvető fogalma, amelyben a csúcsok között míndig létezik legalább egy út. Ez azt jelenti, hogy bármelyik csúcs párja között található olyan útelem, amely ezeket a csúcsokat összeköti.

Alapfogalmak

Gráfok

A gráf egy olyan matematikai struktúra, amely csúcsokból (és általában élekből) áll. Formálisan egy gráf $G=(V,E)$ , ahol:

$V$ a csúcsok halmaza
$E$ az élek halmaza, amelyek a csúcsokat kötik össze

Összefüggő gráf

Egy gráf összefüggő, ha bármely $u,v\in V$ csúcsokra létezik olyan út, amely áthalad a gráf élein, és eljut $u$ -ból $v$ -be.

Irányítatlan és irányított gráfok

Irányítatlan gráf: Az éleknek nincs irányuk, tehát az út oda-vissza bejárható.
Irányított gráf: Az élek irányítottak, vagyis az út csak az élek iránya szerint járható be.

Részgráfok

Egy gráf részgráfja a gráf egy olyan alhalmaza, amely tartalmazza a csúcsok és élek egy részét. Ha a részgráf összefüggő, akkor összefüggő komponensnek nevezzük.

Típusok

Feszítő fa

Egy összefüggő gráf minimális összefüggő részgráfja, amely nem tartalmaz kört, de az összes csúcspontot tartalmazza.

Erősen összefüggő gráf

Irányított gráf esetén erősen összefüggőnek nevezzük, ha bármely $u,v\in V$ csúcsokra van olyan irányított út, amely $u$ -ból $v$ -be vezet, és fordítva is.

Gyengén összefüggő gráf

Egy irányított gráf gyengén összefüggő, ha az irányokat elhagyva a gráf összefüggő.

Tulajdonságok

Komponensek

Egy gráf összefüggő komponensei olyan maximális összefüggő részgráfok, amelyek egymástól függetlenek.

Gráf átmérő

Az összefüggő gráf átmérője a leghosszabb lehetséges minimális út bármelyik két csúcspont között.

Gráf sūrűség

Egy gráf sūrűsége a csúcsok és élek számának aránya:

{\text{Sūrűség}}={\frac {2\cdot |E|}{|V|\cdot (|V|-1)}}

Fontos tételek

Euler-tétel

Egy irányítatlan gráfban létezik Euler-kör (egy olyan kör, amely minden élet pontosan egyszer érint), ha és csak akkor, ha a gráf összefüggő, és minden csúcspont fokszáma páros.

Feszítő fa tétel

Egy összefüggő gráfnak mindig van legalább egy feszítő fája, amely az összes csúcspontot tartalmazza, de pontosan $|V|-1$ éle van.

Alkalmazások

Hálózatok: Kommunikációs hálózatok, elektromos áramkörök tervezése.
Számítógépes grafika: Modellkészítés, körfögások kezelése.
Közlekedési hálózatok: Minimális költségű útvonalak keresése.
Adathalmazok: Klaszterezés és klaszterek közti kapcsolatok elemzése.

Algoritmusok

DFS (Mélységi bejárás)

Egy összefüggő komponens vagy teljes gráf feltérképezésére használt algoritmus.

BFS (Szélességi bejárás)

Alkalmas a legrövidebb utak megtalálására.

Kruskal- és Prim-algoritmus

Mindkettő minimális feszítő fák keresésére szolgál.

Fordítások

angol: undirected graph (en)
orosz: неориентированный граф (ru) (neorijentirovannyj graf)

További információk

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