Graf complet

En el camp matemàtic de la teoria de grafs, un graf complet és un graf simple on una aresta connecta tots els parells de vèrtexs.^[1] El graf complet amb ${\displaystyle n}$ vèrtex té ${\displaystyle n}$ vèrtex i ${\displaystyle n(n-1)/2}$ arestes, i és donat amb ${\displaystyle K_{n}}$. És un graf regular de grau ${\displaystyle n-1}$. Tots els grafs complets són els seus propis cicles. Estan màximament connectats de forma que l'únic tall de vèrtex que desconnecta el graf és tot el conjunt de vèrtexs.

Un graf complet amb n nodes representa les arestes d'un n-símplex. Geomètricament ${\displaystyle K_{3}}$ està relacionat amb un triangle, ${\displaystyle K_{4}}$ amb un tetràedre, ${\displaystyle K_{5}}$ un pentacoron, etc.

El teorema de Kuratowski diu que un graf planar no pot contenir ${\displaystyle K_{5}}$ (o el graf bipartit complet ${\displaystyle K_{3,3}}$) com a menor. Com que ${\displaystyle K_{n}}$ inclou ${\displaystyle K_{n-1}}$, no hi ha grafs ${\displaystyle K_{n}}$ amb ${\displaystyle n>=5}$ que siguin planars.

Una propietat important dels grafs complets és el nombre quadràtic de connexions. Això vol dir que el nombre d'arestes és una funció quadràtica del nombre de nodes. Per tant, un graf complet pot ser el pitjor cas per grans sistemes connectats com xarxes socials i xarxes d'ordinadors.

Els grafs complets amb ${\displaystyle n}$ vèrtex, per a ${\displaystyle n}$ entre 1 i 8, es mostren a continuació amb el nombre de connexions:

${\displaystyle K_{1}:0}$	${\displaystyle K_{2}:1}$	${\displaystyle K_{3}:3}$	${\displaystyle K_{4}:6}$
${\displaystyle K_{5}:10}$	${\displaystyle K_{6}:15}$	${\displaystyle K_{7}:21}$	${\displaystyle K_{8}:28}$

Referències

1. Diestel, Reinhard. «1.1 Graphs». A: Graph Theory (en anglès). Electronic Edition 2000. Nova York: Springer-Verlag, 1997-2000, p. 3. ISBN 3-540-26182-6.

Enllaços externs

• Counting Paths and Cycles in Complete Graphs. Results are available Mehdi Hassani, Cycles in graphs and derangements, Math. Gaz. 88(March 2004) pp. 123-126 (reprint) Arxivat 2007-12-16 a Wayback Machine. or here