Termes de la teoria de grafs
 |
S'ha proposat fusionar aquesta pàgina amb «Glossari de teoria de grafs». (vegeu la discussió, pendent de concretar). Data: abril de 2013 |
 |
Aquest article és manifestament incomplet. Ajudeu a desenvolupar-lo de forma que l'exposició de conceptes o idees sigui coherent, o com a mínim sigui un esborrany amb una estructuració acceptable. |
La teoria de grafs és una branca de les matemàtiques i la informàtica que es dedica a l'estudi dels grafs i les seves propietats. En aquest context, un graf consisteix en una col·lecció de vèrtexs (o nodes) conectats per línies anomenades arestes. La teoria de grafs té un vocabulari especialitzat molt ampli. Alguns autors utilitzen les mateixes paraules per a significats diferents i també es dóna el cas que diferents paraules es refereixen al mateix concepte. Aquest article intenta ser un resum de la utilització de tot aquest vocabulari.
Termes bàsics
Un graf G consisteix en dos tipus d'elements, els vèrtexs i les arestes. Cada aresta té dos extrems dins del conjunt de vèrtex, i es diu que l'aresta connecta o uneix els dos extrems. Una aresta es pot definir per tant mitjançant un conjunt de dos vèrtexs (o un parell ordenat, en el cas d'un graf dirigit - vegeu Secció Direcció).
Existeixen models alternatius de graf; e.g., es pot pensar un graf com una funció binaria booleana en el conjunt de vèrtexs o en una matriu quadrada (0,1).
Un vèrtex (element bàsic) es dibuixa mitjançant un simple node o un punt. El conjunt de vèrtexs de G es denota normalment com V(G), o V quan no hi ha perill de confusió. L'ordre d'un graf és el nombre de vèrtexs, i.e. |V(G)|.
Una aresta (un conjunt de dos elements) es dibuixa com una línia que conecta dos vèrtexs, anomenats extrems. Una aresta amb extrems x i y es denota xy (sense cap símbol al mig). El conjunt d'arestes de G es denota habitualment per E(G), or E quan no hi ha risc de confusió.
La mida d'un graf és el nombre d'arestes del graf, i.e. |E(G)|.
Vegeu també
Referències
 |
Caldria contextualitzar les obres citades al cos de l'article.
Aquest article té una llista de referències o d'enllaços externs, però les fonts no queden clares. Podeu millorar aquest article precisant cadascuna d'aquestes obres en citacions i referències a frases o paràgrafs concrets. |
- [1] Graph Triangulation, Jayson Rome, October 14, 2002 [1]
- Bollobás, Béla (1998). Modern Graph Theory. New York: Springer-Verlag. ISBN 0-387-98488-7. [Packed with advanced topics followed by a historical overview at the end of each chapter.]
- Diestel, Reinhard. Graph Theory. 3rd edition. Graduate Texts in Mathematics, vol. 173, Springer-Verlag, 2005. ISBN 3-540-26182-6. [Standard textbook, most basic material and some deeper results, exercises of various difficulty and notes at the end of each chapter; known for being quasi error-free. Free electronic version is available.]
- West, Douglas B. (2001). Introduction to Graph Theory (2ed). Upper Saddle River: Prentice Hall. ISBN 0-13-014400-2. [Tons of illustrations, references, and exercises. The most complete introductory guide to the subject.]
- Weisstein, Eric W., «Graph» a MathWorld (en anglès).
- Zaslavsky, Thomas. Glossary of signed and gain graphs and allied areas. Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, # DS 8. http://www.combinatorics.org/Surveys/
es:Anexo:Glosario en teoría de grafos he:גרף (תורת הגרפים)#תת גרף ru:Словарь терминов теории графов