„Gráf” változatai közötti eltérés

 

[[Kép:6n-graf.svg|thumb|Címkézett gráf 6 csúccsal és 7 éllel]]

A '''gráf''' a [[matematika]]i [[gráfelmélet]] és a [[számítógéptudomány]] egyik alapvető fogalma. A gráf dolgok (''csomópontok'', ''csúcsok'') és rajtuk értelmezett összeköttetések (''élek'') halmaza. Egy gráfot megadhatunk csúcsainak és éleinek felsorolásával, vagy szemléletesebben egy diagram formájában, ahol a pontok felelnek meg a gráf csúcsainak, az őket összekötő ívek pedig az éleknek. A két megadási mód ekvivalens, azaz a gráf pusztán egy struktúra, semmilyen megjelenítési információt nem tartalmaz, így különböző diagramok is tartozhatnak ugyanahhoz a gráfhoz.

 

Alapértelmezésben a gráf ''irányítatlan'', azaz nem teszünk különbséget „A-ból B-be”, illetve „B-ből A-ba” menő élek között. Ezzel szemben az ''irányított gráf''okban (angolosan: digráf) a két iránynak ''irányított él''ek felelnek meg.

 

<small>Például, ha egy valódi úthálózatban, ahol a csúcsok a csomópontok, az élek az útszakaszok, és ''A''-ból ''B''-be szeretnénk eljutni, de a különböző lehetséges utak nem egyformán kedvezőek, van rövidebb (gyorsabb, olcsóbb), akkor az élekhez az éleknek megfelelő hosszt (időtartamot, árat) rendelve, a válasz a számunkra legkedvezőbb út.</small>

 

[[Kép:7n_graph_with_minimal_spanning_tree2.svg|thumb|Súlyozott gráf a minimális feszítő fájával (piros)]]

<!-- [[Kép:7n_graph_with_minimal_spanning_tree.svg|thumb|Súlyozott gráf a minimális feszítő fájával (piros)]] -->

Súlyozott gráfban:

<small>Egy létesítendő (víz-, csatorna-, számítógép-) hálózattal szemben az az elvárás, hogy ha nem is közvetlenül, de minden csomópontot kössön össze és olcsó legyen kiépíteni. A feladatot leírhatjuk egy súlyozott gráffal, melynek csúcsai a csomópontok, egy él felel meg egy lehetséges hálózati szakasznak, a kiépítési költségével súlyozva. Könnyen belátható, hogy ha a szakaszok nincsenek ingyen, akkor az így kapott legolcsóbb hálózat(ok)ban nem lesz kör (hiszen a kör egyik élét büntetlenül elhagyhatnánk). Az ilyen (összefüggő, körmentes) gráfokat hívják [[fa (gráfelmélet)|fáknak]].</small>

 

===[[PERT módszer|Feladatütemezés]]===

Nemnegatív étékekkel súlyozott irányított gráfban:

:''Milyen hosszú a leghosszabb út ''A''-ból ''B''-be?''

<small>Egy projekt megszervezésénél, a különböző munkafázisokat általában nem lehet egymástól függetelenül végrehajtani. Tegyük fel, hogy a betartandó szabályok csak arra vonatkoznak, hogy egyes munkafázisok meg kell előzzenek másokat adott idővel. Természetesen adódik a kérdés, hogy lehetséges-e egyáltalán az összes szabály betartása, és ha igen mikor ér leghamarabb véget a projekt? A problémához készíthetünk egy súlyozott, [[irányított gráf]]ot, melyben a csúcsok a munkafázisoknak, az irányított élek a betartandó szabályoknak felelnek meg. (Például egy építkezési szabálynak megfelelő él a gráfban: {alap betonozás}&nbsp;–(8)→&nbsp;{falazás}, azaz a két esemény között legalább 8 napnak kell eltelnie.) Ha ebben a gráfban van [[irányított kör]] az biztosan [[holtpont|patthelyzet]]hez vezet, hiszen ekkor néhány munkafázis közvetve a saját befejeződésére várna, ekkor nincs olyan [[topologikus sorrend|végrehajtási sorrend]], mely a szabályoknak eleget tenne. Megmutatható, hogy ha a gráf [[DAG|körmentes]], akkor a feladat mindig megoldható. Hogy legkorábban mikorra készül el a projekt, azt egy leghosszabb út(ak) hossza árulja el, amelyeket hívnak '''''kritikus ut'''''aknak is. A leggyorsabb befejezéshez tartozó ütemezés megtalálására van gyors (polinom idejű) algoritmus, melynek általánosabb szabályokra is felkészített változatait sok üzleti szoftver ([[projektmenedzsment]]) is tartalmazza. (lásd: [[PERT módszer]])</small>

 

=== [[Párosítás (gráfelmélet)|Párosítás]]ok ===

 

Irányítatlan gráfban egy él két csúcsot állít párba.

<!-- <math>(\mbox{beton kész})</math> <math>(\mbox{beton kész})\longrightarrow^{8}(\mbox{falazást kezd})</math> -->

 

=== [[Színezés (gráfelmélet)|Színezés]]ek ===

Egyszerű gráfban:

:''Legkevesebb hány szín kell a csúcsok kiszínezéséshez, ha a szomszédosak nem lehetnek egyszínűek?''