A matematika, azon belül a gráfelmélet területén egy mediángráf (median graph) olyan irányítatlan gráf, melynek tetszőlegesen választott a, b, c csúcsa egyedi mediánnal rendelkezik: a statisztikában ismert medián alatt gráfokban olyan m(a,b,c) csúcs értendő, amely része az a, b és c csúcspárjai közötti mindhárom legrövidebb útnak.
A mediángráfok tanulmányozása már régóta tart, az első fecskék közé tartozik vagy (explicitebben) tanulmánya, de a „mediángráf” kifejezés először -nél jelent meg. Ahogy Chung, Graham és Saks írja, „a mediángráfok természetes módon felbukkannak a rendezett halmazok és diszkét disztributív hálók tanulmányozásakor, kiterjedt irodalmuk van”.. A filogenetikus rendszertanban a maximális parszimóniájú leszármazási fákat megtestesítő Buneman-gráf is egy mediángráf.; ; . A mediángráfok a választáselméletben is előbukkannak: ha alternatívák egy halmaza mediángráf-szerkezetű, lehetséges az alternatívák közötti többségi preferencia egyértelmű meghatározása.; .
A mediángráfok további áttekintését adják: , és .
Példák
Minden fa mediángráf., Proposition 1.26, p. 24. Ennek belátásához vegyük észre, hogy egy fában az a, b és c csúcsok alkotta párok közötti három legrövidebb út uniója vagy maga is egy út, vagy egy három fokszámú csúcsban találkozó három út által alkotott részfa. Az első esetben, tehát ha az utak uniója is egy út, akkor az m(a,b,c) medián megegyezik a, b vagy c közül azzal, amelyik a másik két csúcs közötti úton helyezkedik el. A második esetben, ha az utak uniója alkotta részfa nem egy út, akkor a medián a részfa középponti helyzetű, három fokszámú csúcsa.
A fákon kívül mediángráfok még a rácsgráfok is. Egy rácsgráfban az m(a,b,c) medián koordinátái megegyeznek az a, b és c csúcsok koordinátáinak mediánjával. Megfordítva, bármely mediángráf csúcsai címkézhetők rácspontokkal úgy, hogy a mediánok az előbb említett módon koordinátákkal számíthatók legyenek.Ez azonnal nyilvánvaló a mediángráfok a hiperkockákból összehúzással (retrakcióval) megkapható gráfokként történő, alább leírt jellemzéséből.
A négyszöggráfok szintén a mediángráfok közé tartoznak; ezek olyan síkgráfok, melyekben az összes belső tartomány négyszög alakú és minden belső csúcs négy vagy több éllel érintkezik.; ; . Egy poliominó a négyszöggráfok speciális esete, ezért mindig mediángráfot alkot.
Tetszőleges G irányítatlan gráf szimplexgráfja, κ(G) minden csúcsa a G egy-egy klikkjének (teljes részgráfjának) felel meg; a κ(G) két csúcsát akkor köti össze él, ha a megfelelő klikkek G egy csúcsával térnek el. A szimplex gráf minden esetben mediángráf, melyben bármely klikkhármas mediánja a többségi szabály alapján meghatározható, kiválasztva hogy a klikkek melyik csúcsait tartalmazza., page 200.
A négy hosszúságú körgráfon kívül egy körgráf sem lehet mediángráf. Az ilyen körgráfokban mindig kiválaszthatók úgy az a, b és c csúcsok, hogy a három legrövidebb út megkerülje a teljes kört anélkül, hogy lenne közös metszetük. Az ilyen csúcshármasoknak pedig nincs mediánjuk.
Ekvivalens meghatározások Egy gráf tetszőleges két csúcsa, a és b közötti élek minimális számát a csúcsok távolságának nevezzük, jelölése d(a,b). Az a és b közötti legrövidebb utakon található csúcsok intervallumát így definiáljuk: I(a,b) = {v | d(a,b) = d(a,v) + d(v,b)}. A mediángráf definíciója alapján bármely három a, b és c csúcsához tartozó intervallumok egyetlen pontban metszik egymást: Minden a, b és c-re |I(a,b) ∩ I(a,c) ∩ I(b,c)| = 1.
Ekvivalens definíció szerint bármely három a, b és c csúcshoz található olyan m(a,b,c) csúcs, amire a gráfban a súlyozatlan különbségek kielégítik a következő egyenlőtlenségeket: d(a,b) = d(a,m(a,b,c)) + d(m(a,b,c),b) d(a,c) = d(a,m(a,b,c)) + d(m(a,b,c),c) d(b,c) = d(b,m(a,b,c)) + d(m(a,b,c),c) és m(a,b,c) az egyetlen csúcs, amire ez igaz.
A mediángráfok előállnak még 2-kielégíthetőségi problémák megoldáshalmazaként, hiperkockagráfok retrakciójával, véges medián algebrák gráfjaiként, Helly-féle split rendszerek Buneman-gráfjaiként és a 2 windexű gráfokként; lásd az alábbi szakaszokat.
Disztributív hálók és mediánalgebrák
A hálóelmélet területén egy véges háló gráfjának csúcsait a háló elemei alkotják, két csúcs között pedig akkor húzódik él, ha a hozzájuk tartozó elemek a hálóban fedési relációban vannak. A hálók szemléltetése gyakran Hasse-diagramjukkal történik, melyek a hálók gráfjainak lerajzolásai. Ezek a gráfok, különösen a disztributív hálók esetében, a mediángráfok közeli rokonai.
Egy disztributív hálóban Birkhoff a következőképpen definiálta az önduális, háromváltozós medián műveletet: szerint a művelet első definíciója itt látott napvilágot: . m(a,b,c) = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c), ami kielégít egyes axiómákat, amiket a 0 és 1 közötti számok szokásos mediánja, általánosabban pedig a mediánalgebrák is kielégítenek: Idempotencia: m(a,a,b) = a minden a-ra és b-re. Kommutativitás: m(a,b,c) = m(a,c,b) = m(b,a,c) = m(b,c,a) = m(c,a,b) = m(c,b,a) bármely a, b, c hármasra. Disztributivitás: m(a,m(b,c,d),e) = m(m(a,b,e),c,m(a,d,e)) bármely a, b, c, d, e ötösre. Neutrális elemek: m(0,a,1) = a minden a-ra. A disztributivitás követelménye felcserélhető az asszociativitással:, p. 65, and exercises 75 and 76 on pp. 89–90. Knuth states that a simple proof that associativity implies distributivity remains unknown. Asszociativitás: m(x,w,m(y,w,z)) = m(m(x,w,y),w,z) A mediánképzés művelete segítségével definiálható egyfajta intervallum a disztributív hálókon: I(a,b) = {x | m(a,x,b) = x} = {x | a ∧ b ≤ x ≤ a ∨ b}.Az egyenletben szereplő két kifejezés közötti ekvivalenciához, lásd , Theorem 1. Egy véges disztributív háló gráfjában a és b csúcsok közt akkor húzódik él, ha I(a,b) = {a,b}. Ennek a gráfnak bármely a és b csúcspárjára a fent hálóelméleti kifejezésekkel meghatározott I(a,b) intervallum az a-ból b-be vezető legrövidebb utakon lévő csúcsokból áll, így egybeesik a korábban gráfelméleti alapokon definiált intervallumokkal. Bármely a, b és c hálóelemre az m(a,b,c) a három intervallum, I(a,b), I(a,c) és I(b,c) egyedi metszetét alkotja., Theorem 2. Ezért bármely véges disztributív háló gráfja mediángráf. Megfordítva, ha egy G mediángráfban létezik két olyan, 0-val és 1-gyel jelölt csúcs, melyek közötti legrövidebb úton az összes többi csúcs megtalálható (ekvivalens megfogalmazásban m(0,a,1) = a minden a-ra), akkor definiálható az a disztributív háló, melyben a ∧ b = m(a,0,b) és a ∨ b = m(a,1,b), G pedig ennek a hálónak a gráfja lesz., p. 751.
a disztributív hálók gráfjait úgy karakterizálja, mint hiperkockák átmérőt megtartó retrakcióit. Általánosabban, minden mediángráfban meghatározható egy m ternáris művelet idempotenciával, kommutativitással és disztributivitással, igaz, potenciálisan egy disztributív háló neutrális elemeit nélkülözve. Bármely véges halmazon értelmezett ternáris művelet, ami rendelkezik ezzel a három tulajdonsággal (de nem feltétlenül vannak 0 és 1 elemei) ugyanilyen módon egy mediángráfot határoz meg..
Konvex halmazok és Helly-családok Mediángráfban egy S csúcshalmazt akkor tekintünk konvexnek, ha az S-be tartozó bármely a és b csúcsára igaz, hogy az I(a,b) intervallum összessége az S részhalmaza. Ekvivalens megfogalmazásban, az intervallumokra fent adott két definíció alapján S akkor konvex, ha bármely két csúcsa közötti összes legrövidebb utat tartalmazza, vagy ha tartalmazza minden olyan ponthármas mediánját, melynek legalább két pontja S-beli. Észrevehető, hogy bármely két konvex halmaz metszete is konvex. az ilyen halmazokat „ideálnak” nevezi, de fontos megkülönböztetni a disztributív háló konvex halmazait jelentő ideálokat a háló ideáljától.
A mediángráf konvex halmazai Helly-tulajdonságúak: ha F egymást páronként metsző konvex halmazok tetszőleges családja, akkor F összes halmazának is van nem üres közös metszete., Theorem 2.40, p. 77. Hiszen, ha F csak három konvex halmazzal rendelkezik, legyenek ezek S, T és U, az S és T metszete legyen a, a T és U metszete legyen b, az S és U metszete pedig legyen c, akkor a konvexitás miatt minden a és b közötti legrövidebb útnak T-n belül kell lennie, és hasonlóan a másik két pár közötti útnak is a megfelelő két halmazban kell lennie; de m(a,b,c) mindhárom pár közötti útba beletartozik, tehát mindhárom halmaz része, így a közös metszetet alkotja. Ha F-nek háromnál több konvex halmaza van, akkor a halmazok számára vonatkozó indukcióval látható be az állítás; hiszen bármely F-beli halmazpárt felcserélve a metszetükkel, a halmazhármasokra való eredményt felhasználva igazolható, hogy a lecserélt család továbbra is páronként metszésben van.
A mediángráfok konvex halmazainak egy különösen fontos, az euklideszi terek féltereihez hasonló szerepet játszó családja, a Wuv = {w | d(w,u) < d(w,v)} a gráf minden uv éléhez meghatározott halmazokból áll. Magyarán Wuv azokból a csúcsokból áll, melyek közelebb állnak u-hoz mint v-hez, vagy ekvivalens megfogalmazás szerint azok a w csúcsok, melyekre a v-ből w-be vezető legrövidebb utak közül legalább egy u-n megy keresztül. Annak megmutatásához, hogy Wuv konvex, legyen w1w2...wk tetszőleges, Wuv-n belül kezdődő és ott is végződő legrövidebb út; ekkor w2 szintén Wuv-n belül található, különben a csúcsok közti lehetséges távolságok figyelme vételével megmutatható lenne, hogy a két pont, m1 = m(u,w1,wk) és m2 = m(m1,w2...wk) az u, w1 és wk különböző mediánjai lennének, ami ellentmond a mediángráf definíciójának, ami megköveteli a mediánok egyediségét. Ezért a Wuv két csúcsa közötti legrövidebb úton minden egymást követő csúcs is Wuv-beli, ezért Wuv-nek tartalmaznia kell a csúcsok közötti összes legrövidebb utat, ami éppen a konvexitás egyik definíciója.
A Wuv halmazok Helly-tulajdonsága fontos szerepet játszik a mediángráfok 2-kielégíthetőségi kifejezésekként való karakterizálásában, lásd lejjebb.
2-kielégíthetőség (2-SAT) A mediángráfok közeli kapcsolatban állnak a 2-kielégíthetőségi problémák megoldáshalmazaival, aminek segítségével jellemezni lehet ezeket a gráfokat, továbbá kapcsolatba hozhatók hiperkockák szomszédságtartó leképezéseivel., Proposition 2.5, p.8; ; ; , Theorem S, p. 72.
Egy 2-kielégíthetőségi kifejezés logikai változók és ún. „klózok” (a változópárokon értelmezett megkötések, melyek megkövetelik egyes értékkombinációk elkerülését) gyűjteményéből áll. Az ilyen problémákat általában konjunktív normálformában fejezik ki, melyben az egyes klózok diszjunkcióként szerepelnek, a megkötések összessége pedig klózok konjunkciójaként van felírva, például a következő formában:
Egy ilyen kifejezés megoldásában olyan igazságértékek vannak hozzárendelve a változókhoz, melyek az összes klózt kielégítik, tehát a konjunktív normálformájú kifejezésbe behelyettesítve őket a kifejezés igaz értéket kap. Az összes megoldás családjának természetes szerkezete egy mediánalgebra, ahol három megoldás mediánja úgy kapható meg, hogy minden igazságérték a három megoldás értékeiből többségi függvénnyel képzett értéket veszi fel; könnyen ellenőrizhető, hogy ez a medián megoldás nem sértheti meg egyetlen klózt sem. Ezért a megoldások mediángráfot alkotnak, melyben egy megoldás szomszédja megkapható változók olyan halmazának negálásával, melyeknek egymással egyenlőnek vagy ellentétesnek kell lenniük a megkötések alapján.