Anar al contingut

Grafo mijà

De L'Enciclopèdia, la wikipedia en valencià
El mijà de tres vèrtiços en un 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:

"Els grafos mijans sorgixen naturalment de l'estudi dels conjunts ordenats i dels retículs distributivos discrets, i posseïxen una extensa lliteratura."[1]

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

El mijà m(a,b,c) de tres vèrtiços a, b i c en un arbre, mostrant el subárbol format per l'unió dels camins més curts entre dits vèrtiços.

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]

Un grafo quadrat.

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

Referències