Teoria de grafs

Representació d'un graf amb 6 vèrtexs i 7 arestes

La teoria de grafs és una branca de les matemàtiques i la informàtica que es dedica a l'estudi dels grafs, estructures matemàtiques utilitzades per a modelitzar relacions entre parelles d'objectes.[1] En aquest context, un graf consisteix en una col·lecció de vèrtexs o nodes connectats per línies anomenades arestes. Els grafs poden ser no dirigits, és a dir sense fer distinció entre els dos vèrtexs associats a cada aresta, o dirigits, les arestes dels quals van d'un vèrtex a un altre; en aquest cas, les arestes s'anomenen arcs. Els grafs se solen representar gràficament amb un punt o cercle per cada vèrtex, i una línia entre vèrtexs connectats. Si el graf és dirigit, els arcs se simbolitzen amb fletxes, indicant la direcció de la relació entre els dos vèrtexs.

Els grafs són un dels principals objectes d'estudi de la matemàtica discreta. Les aplicacions de la teoria de grafs giren al voltant d'estructures que poden ser sistematitzades amb grafs, com per exemple l'estructura de llocs web, l'anàlisi de xarxes, l'estudi de molècules en química i física, o altres camps com els estudis sociològics.

El precursor de la teoria de grafs fou Leonhard Euler, que la va iniciar tot intentant resoldre el problema dels set ponts de Königsberg.

Altres idiomes
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
吴语: 图论
中文: 图论
粵語: 圖論