Introducció als grafs: diferència entre les revisions
De FFAWiki
(Es crea la pàgina amb «== Grafs == === Definicions === === Propietats === === Tipus especials de grafs === === Isomorfisme de grafs === === Operacions amb grafs === === La seqüència de graus d’un graf === == Variants de grafs == ===Grafs dirigits=== ===Multigrafs=== ===Grafs ponderats=== ==Connexió i components== ===Connexió en el cas de grafs=== ===Connexió en el cas de digrafs=== ==Grafs plans== ===Propietats=== ==Coloració d'un graf== ===Propietats=== ==Emmagatzematge d'...».) |
|||
| (Hi ha 13 revisions intermèdies del mateix usuari que no es mostren) | |||
| Línia 2: | Línia 2: | ||
=== Definicions === | === Definicions === | ||
== Variants de grafs == | :*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|423x423px]] | |||
:*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: | |||
:** <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=== | |||
:*'''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]] | |||
:* '''Graf complet'''. K<sub>n</sub> on n es mes gran o igual a 2. Te n vèrtexs i totes les aretes possibles. | |||
:** K <sub>3</sub> | |||
::[[Fitxer:ExempleGrafK3.png|310x310px]] | |||
:* '''Graf cicle'''. C<sub>n</sub> on n es mes gran o igual a 3 cada vèrtex esta connectat per dos arestes formant un cicle. | |||
:** C<sub>4</sub> | |||
::[[Fitxer:ExempleGrafC4.png|291x291px]] | |||
:* '''Graf trajecte'''. T<sub>n</sub> on n es mes gran o igual a 2 cada vèrtex està connectat per dos arestes menys l'últim i el primer que nomes en tenen una formant un trajecte | |||
:** T<sub>3</sub> | |||
::[[Fitxer:ExempleGrafT3.png|319x319px]] | |||
:* Graf bipartit. Els vèrtex es poden separar en dos subconjunts en les que cada vèrtex d'un grup no esta connectat directament entre si. | |||
:* Graf bipartit complet. Els vèrtex es poden separar en dos subconjunts en les que cada vèrtex d'un grup no esta connectat directament entre si. Te totes les arestes que complexin la norma de l'esmentat anteriorment. | |||
::[[Fitxer:ExempleGrafK33.png|132x132px]] | |||
===Isomorfisme de grafs=== | |||
:* Dos grafs són isomorfs si canviant els noms d'un dels grafs els dos es poden representar de la mateixa manera tenint els mateixos vèrtex i arestes. | |||
::[[Fitxer:ExempleGrafIsomorfisme.png|570x570px]] | |||
===Operacions amb grafs=== | |||
===La seqüència de graus d’un graf=== | |||
==Variants de grafs== | |||
===Grafs dirigits=== | ===Grafs dirigits=== | ||
===Multigrafs=== | ===Multigrafs === | ||
===Grafs ponderats=== | ===Grafs ponderats=== | ||
| Línia 20: | Línia 60: | ||
==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ó de 12:08, 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.
- Un Graf G(V,A) esta format per vèrtexs (V) i les connexions entre vèrtexs, les arestes (A).
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
- Graf r-regular. Tots els vèrtex amb el mateix grau r
- 3-regular
- Graf complet. Kn on n es mes gran o igual a 2. Te n vèrtexs i totes les aretes possibles.
- K 3
- Graf cicle. Cn on n es mes gran o igual a 3 cada vèrtex esta connectat per dos arestes formant un cicle.
- C4
- Graf trajecte. Tn on n es mes gran o igual a 2 cada vèrtex està connectat per dos arestes menys l'últim i el primer que nomes en tenen una formant un trajecte
- T3
- Graf bipartit. Els vèrtex es poden separar en dos subconjunts en les que cada vèrtex d'un grup no esta connectat directament entre si.
- Graf bipartit complet. Els vèrtex es poden separar en dos subconjunts en les que cada vèrtex d'un grup no esta connectat directament entre si. Te totes les arestes que complexin la norma de l'esmentat anteriorment.
- Graf nul. Nn On n es mes petit o igual a 1. Te n vèrtex i 0 arestes.
Isomorfisme de grafs
- Dos grafs són isomorfs si canviant els noms d'un dels grafs els dos es poden representar de la mateixa manera tenint els mateixos vèrtex i arestes.
