Introducció als grafs: diferència entre les revisions
De FFAWiki
| Línia 4: | Línia 4: | ||
:*Un Graf G(V,A) esta format per vèrtexs (V) i les connexions entre vèrtexs, les arestes (A). | :*Un Graf G(V,A) esta format per vèrtexs (V) i les connexions entre vèrtexs, les arestes (A). | ||
: | :**V = {1, 2, 3, 4, 5} | ||
: | :**A = <nowiki>{{1, 2}, {5, 1}, {5, 4}, {4, 2}, {3, 4}, {3, 5}, {2, 3}}</nowiki> | ||
[[Fitxer:ExempleGraf.png | [[Fitxer:ExempleGraf.png|423x423px]] | ||
:*Un graf com a tal no te multiplicitat d'arestes ni vèrtexs que connecten amb si mateix. | :*Un graf com a tal no te multiplicitat d'arestes ni vèrtexs que connecten amb si mateix. | ||
:*Els graf amb multiplicitat d'arestes s'anomenen '''Multigrafs'''. | :*Els graf amb multiplicitat d'arestes s'anomenen '''Multigrafs'''. | ||
| Línia 14: | Línia 13: | ||
===Propietats=== | ===Propietats=== | ||
:* El nombre d'arestes d'un graf: | :* El nombre d'arestes d'un graf: | ||
: | :** <nowiki>n*(n-1)/2</nowiki> | ||
:* El nombre d'arestes d'un pseudograf: | :* El nombre d'arestes d'un pseudograf: | ||
: | :** <nowiki>n*(n+1)/2</nowiki> | ||
:*Lema de les encaixades: | :*Lema de les encaixades: | ||
: | :**La suma de tots els graus dels vèrtexs d'un graf o pseudograf és igual a dues vegades el nombre d'arestes. | ||
:*El nombre de vèrtexs de grau senar d'un graf és parell. | :*El nombre de vèrtexs de grau senar d'un graf és parell. | ||
===Tipus especials de grafs=== | ===Tipus especials de grafs=== | ||
===Isomorfisme de grafs === | :*'''Graf nul'''. N<sub>n</sub> On n es mes petit o igual a 1. Te n vèrtex i 0 arestes. | ||
:**N<sub>4</sub> [[Fitxer:ExempleGrafNul.png|239x239px]] | |||
:*'''Graf r-regular'''. Tots els vèrtex amb el mateix grau r | |||
:**3-regular [[Fitxer:ExempleGraf3regular.png|282x282px]] | |||
===Isomorfisme de grafs=== | |||
===Operacions amb grafs=== | ===Operacions amb grafs=== | ||
===La seqüència de graus d’un graf === | ===La seqüència de graus d’un graf=== | ||
==Variants de grafs== | ==Variants de grafs== | ||
===Grafs dirigits=== | ===Grafs dirigits=== | ||
===Multigrafs=== | ===Multigrafs === | ||
===Grafs ponderats=== | ===Grafs ponderats=== | ||
| Línia 38: | Línia 42: | ||
==Coloració d'un graf== | ==Coloració d'un graf== | ||
===Propietats=== | ===Propietats=== | ||
==Emmagatzematge d'un graf en memòria== | ==Emmagatzematge d'un graf en memòria == | ||
===Matriu d'adjacència=== | ===Matriu d'adjacència=== | ||
===Llistes d'adjacència=== | ===Llistes d'adjacència=== | ||
Revisió del 10:39, 21 maig 2023
Grafs
Definicions
- Un Graf G(V,A) esta format per vèrtexs (V) i les connexions entre vèrtexs, les arestes (A).
- V = {1, 2, 3, 4, 5}
- A = {{1, 2}, {5, 1}, {5, 4}, {4, 2}, {3, 4}, {3, 5}, {2, 3}}
- Un Graf G(V,A) esta format per vèrtexs (V) i les connexions entre vèrtexs, les arestes (A).
- Un graf com a tal no te multiplicitat d'arestes ni vèrtexs que connecten amb si mateix.
- Els graf amb multiplicitat d'arestes s'anomenen Multigrafs.
- Les arestes que connecten un vèrtex amb si mateix s'anomenen llaços i el graf passa a anomenar-se pseudograf.
Propietats
- El nombre d'arestes d'un graf:
- n*(n-1)/2
- El nombre d'arestes d'un pseudograf:
- n*(n+1)/2
- Lema de les encaixades:
- La suma de tots els graus dels vèrtexs d'un graf o pseudograf és igual a dues vegades el nombre d'arestes.
- El nombre de vèrtexs de grau senar d'un graf és parell.
- El nombre d'arestes d'un graf:
Tipus especials de grafs
- Graf nul. Nn On n es mes petit o igual a 1. Te n vèrtex i 0 arestes.
- N4
- N4
- Graf r-regular. Tots els vèrtex amb el mateix grau r
- 3-regular
- 3-regular
- Graf nul. Nn On n es mes petit o igual a 1. Te n vèrtex i 0 arestes.
