irányított gráf

Magyar

Kiejtés

• IPA: [ ˈiraːɲiːtodɡraːf]

Főnév

irányított gráf

1. (matematika, gráfelmélet) Legyen $A$ egy halmaz, $\rho$ egy reláció $A$-n. Ekkor az $(A,\rho )$ rendezett párt irányított gráfnak hívjuk. Az $A$ halmaz elemeit a gráf pontjainak, a $\rho$ relációt pedig a gráf éleinek nevezzük. Egy $(a,b)\in \rho$ él esetében az $a$ pontot az él kezdőpontjának, a $b$ pontot pedig az él végpontjának hívjuk. Egy $(a,a)$ élt hurokélnek nevezünk.

---

Az irányított gráf (digraph, directed graph) egy speciális gráf, ahol az élek (kapcsolatok) irányítottak, tehát minden él egy rendezett pár ( (u, v) ), ahol az él csak ( u )-ból ( v )-be vezet, és nem fordítva (kivéve, ha egy másik él külön ezt is definiálja). Az irányított gráfokat gyakran használják olyan rendszerek modellezésére, ahol a kapcsolatok aszimmetrikusak.

Formális definíció

Egy irányított gráf ( G ) egy rendezett pár: [ G = (V, E) ] ahol: - ( V ): a gráf csúcsainak (pontjainak) halmaza, - ( E ): rendezett élek halmaza (( E V V )).

Példa

Egy irányított gráf ( G = (V, E) ), ahol: - ( V = {A, B, C} ), - ( E = {(A, B), (B, C), (C, A)} ).

Ez azt jelenti, hogy van egy él ( A )-ból ( B )-be, egy él ( B )-ből ( C )-be, és egy él ( C )-ből ( A )-ba.

Irányított gráf típusai

1. Súlyozott irányított gráf: Az élekhez súlyok vannak rendelve, például távolság vagy költség.
2. Aciklikus irányított gráf (DAG): Olyan irányított gráf, amely nem tartalmaz kört (például feladatütemezési problémák modellezésére használják).
3. Erősen összefüggő gráf: Olyan irányított gráf, ahol bármely két csúcs között létezik irányított út mindkét irányban.

Alapvető fogalmak irányított gráfokban

1. Bejövő fokszám (( )): Egy csúcsra érkező élek száma.
2. Kimenő fokszám (( )): Egy csúcsból induló élek száma.
3. Út: Csúcsok sorozata, ahol minden csúcsot egy irányított él köt össze a következő csúccsal.
4. Kör: Olyan út, amely ugyanabba a csúcsba tér vissza, ahonnan indult.

Példák az irányított gráf alkalmazására

1. Hálózati útvonalak: Az internet forgalmának irányítása, ahol az adatok egy adott irányban áramlanak.
2. Ütemezési problémák: Feladatok sorrendjének meghatározása (például projektek tevékenységi hálója).
3. Adatáramlás: Folyamatok modellezése (például áramlások vagy algoritmusok lépései).
4. Szociális hálók: Kapcsolatok elemzése, például egyoldalú kapcsolatok (Twitter követések).

Fordítások

• angol: directed graph (en), digraph (en)
• német: gerichteter Graph (de)
• orosz: ориентированный граф (ru) (orijentirovannyj graf), орграф (ru) (orgraf)

További információk

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