![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Median_graph.svg/langhu-640px-Median_graph.svg.png&w=640&q=50)
Mediángráf
matematikai fogalom a gráfelméletben / From Wikipedia, the free encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Median_graph.svg/220px-Median_graph.svg.png)
A mediángráfok tanulmányozása már régóta tart, az első fecskék közé tartozik (Birkhoff & Kiss 1947) vagy (explicitebben) (Avann 1961) tanulmánya, de a „mediángráf” kifejezés először (Nebeský 1971)-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”.[1] A filogenetikus rendszertanban a maximális parszimóniájú leszármazási fákat megtestesítő Buneman-gráf is egy mediángráf.[2] 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.[3]
A mediángráfok további áttekintését adják: (Klavžar & Mulder 1999), (Bandelt & Chepoi 2008) és (Knuth 2008).