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

128 bájt hozzáadva ,  14 évvel ezelőtt
képek átrendezése
a (→‎Szinezések: typo: szinezés -> színezés mindenütt)
(képek átrendezése)
 
[[Kép:6n-graf.svg|thumb|Címkézett gráf 6 csúccsal és 7 éllel]]
[[Kép:Directed graph.svg|thumb|Irányított gráf]]
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.
 
[[Kép:4n_digraph_with_cycle.svg‎|thumb|Irányított gráf, benne irányított kör (piros)]]
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>
 
===[[Minimális feszítő fa]]===
[[Kép:7n_graph_with_minimal_spanning_tree2.svg|thumb|Súlyozott gráf a minimális feszítő fájával (piros)]]
===[[Minimális feszítő fa]]===
<!-- [[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>
 
[[Kép:5n_PERT_graph_with_critical_path2.svg|thumb|Egy legalább 7 egység végrehajtási idejű terv a kritikus úttal (piros)]]
[[Kép:4n_digraph_with_cycle.svg‎|thumb|Irányított gráf, benne irányított kör (piros)]]
===[[PERT módszer|Feladatütemezés]]===
 
[[Kép:5n_PERT_graph_with_critical_path2.svg|thumb|Egy legalább 7 egység végrehajtási idejű terv a kritikus úttal (piros)]]
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>
 
[[Kép:Bipartite_graph_with_matching.svg‎ |thumb|Párosítás (piros) páros gráfban]]
=== [[Párosítás (gráfelmélet)|Párosítás]]ok ===
[[Kép:Bipartite_graph_with_matching.svg‎ |thumb|Párosítás (piros) páros gráfban]]
 
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> -->
 
[[Kép:3-coloringEx.svg|thumb|3 színnel színezett egyszerű gráf, kevesebb szín használata már azonos színű szomszédokat eredményezne]]
=== [[Színezés (gráfelmélet)|Színezés]]ek ===
[[Kép:3-coloringEx.svg|thumb|3 színnel színezett egyszerű gráf]]
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?''
321

szerkesztés