Grafo mijà

En matemàtica, i més específicament en la teoria de grafos, un grafo mijà és un grafo no dirigit en que qualssevol tres vèrtiços a, b, i c tenen un únic mijà. Un mijà és un vèrtiç m(a,b,c) que pertany als camins més curts entre qualsevol parell de nodos conformat per a, b, i c.
El concepte de grafo mijà ha segut largamente estudiat, per eixemple, per Birkhoff y Kiss (1947) o (més explícitament) per Avann (1961), pero el primer artícul en cridar-los "grafos mijans" apareix en Nebesk'i (1971). Chung, Graham, i Saks escriuen:
En filogènia, el grafo de Buneman que representa tots els arbres filogenético de màxima parsimònia és un grafo mijà.[2] Els grafos mijans també apareixen en la teoria d'elecció social: si un conjunt d'alternatives té una estructura d'un grafo mijà, és possible derivar una elecció no ambigua de les millors preferències possibles entre elles.[3]
En Klavžar y Mulder (1999),Bandelt y Chepoi (2008) i Knuth (2008) es presenten "Surveys" (artículs científics que presenten estats de l'art sobre un tòpic determinat) sobre grafos mijans.
Eixemples

Qualsevol arbre és un grafo mijà.[4] Per a vore açò, note que en un arbre, l'unió dels tres camins més curts entre qualssevol tres vèrtiços a, b i c pot ser:
- un camí en sí mateixa, en el cas del qual la mijana m(a,b,c) és igual a un dels nodos a, b o c, ya que algun d'ells es trobarà entre els atres dos en el camí, o be
- un subárbol format per tres camins conectats en un únic nodo central de grau tres, en el cas del qual la mijana m(a,b,c) correspon a dit nodo central.
Eixemples adicionals de grafos mijans són els grafos reticulats (lattice graphs en anglés). En un grafo reticulado, les coordenades de la mijana m(a,b,c) poden trobar-se com la mijana de les coordenades de a, b i c. Per un atre costat, en cada grafo mijà un pot etiquetar els vèrtiços com a punts en un retícul sancer de tal manera que les mijanes poden calcular-se satisfactòriament.[5]

Els grafos quadrats, que són grafos planars en que totes les superfícies interiors són quadrilàters i tots els vèrtiços interiors tenen quatre o més arestes incidents, són una atra subclasse de grafos mijans.[6] Un poliominó és un cas especial d'un grafo quadrat, i per lo tant també forma un grafo mijà.
El grafo simple κ(G) de qualsevol grafo no dirigit G té un nodo per a cada clique (subgrafo complet) de G; dos nodos són enllaçats per una aresta si el clique corresponent diferix en un vèrtiç. La mijana de qualssevol tres cliques pot ser formada utilisant la regla de mayoració per a determinar qué vèrtiços dels cliques incloure; el grafo simple és un grafo mijà en que esta regla determina la mijana de qualssevol tres vèrtiços.
Cap grafo cicle de tamany distint de quatre pot ser un grafo mijà, perque qualsevol d'eixos cicles té tres vèrtiços a, b i c tals que els tres camins més curts involucren totes les possibilitats al voltant del cicle sense conseguir una intersecció comuna. Per a una cicle de tamany tres, no pot haver una mijana.
Definicions equivalents
En qualsevol grafo, per a qualssevol dos vèrtiços a i b, es definix el interval dels vèrtiços que es troben en els camins més curts com:
- I(a,b) = {v | d(a,b) = d(a,v) + d(v,b)}.
Un grafo mijà és definit per la propietat que, per a qualssevol tres vèrtiços a, b i c, estos intervals es intersecan en un únic punt:
- Per a tot a, b i c, |I(a,b) ∩ I(a,c) ∩ I(b,c)| = 1.
Equivalentement, per a cada tres vèrtiços a, b i c un pot trobar un vèrtiç m(a,b,c) tal que les distàncies sense pes en el grafo satisfan les inecuacions
- 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)
i m(a,b,c) és l'únic vèrtiç per al qual açò és verdader.
També és possible definir grafos mijans com els conjunts solució de problemes 2-SAT, com els replecs de hipercubos, com els grafos de àlgebra mijanes finitas, com els grafos de Buneman de sistemes de tall de Helly, i com els grafos de windex 2.
Notes
- ↑ Chung, Graham y Saks (1987).
- ↑ Buneman (1971);Dress et al. (1997);Dress, Huber y Moulton (1997).
- ↑ Bandelt y Barthélémy (1984);Day y McMorris (2003).
- ↑ Imrich y Klavžar (2000), Proposició 1.26, p. 24.
- ↑ Açò es conclou immediatament a partir de la caracterisació de grafos mijans com a replecs de hipercubos, descrita més avall.
- ↑ Soltan, Zambitskii y Prisˇacaru (1973);Chepoi, Dragan y Vaxès (2002);Chepoi, Fanciullini y Vaxès (2004).
Referències
- Este artícul conté una traducció derivada de «Grafo mediano» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.