Introducció als grafs: diferència entre les revisions
De FFAWiki
Cap resum de modificació |
|||
| Línia 15: | Línia 15: | ||
:* El nombre d'arestes d'un graf: | :* El nombre d'arestes d'un graf: | ||
::*<nowiki>n*(n-1)/2</nowiki> | ::*<nowiki>n*(n-1)/2</nowiki> | ||
:* El nombre d'arestes d'un pseudograf: | |||
::*<nowiki>n*(n+1)/2</nowiki> | |||
:*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. | |||
===Tipus especials de grafs=== | ===Tipus especials de grafs=== | ||
===Isomorfisme de grafs === | ===Isomorfisme de grafs === | ||
Revisió del 11:25, 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 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.
