Introducció als grafs - Historial de revisió

Mayola: /* Isomorfisme de grafs */

2023-05-21T11:08:52Z

Isomorfisme de grafs

← Versió més antiga		Revisió del 11:08, 21 maig 2023
Línia 42:		Línia 42:
	===Isomorfisme de grafs===		===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 ~~vertex~~ i arestes		:* 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===		===Operacions amb grafs===

Mayola: /* Isomorfisme de grafs */

2023-05-21T11:07:29Z

Isomorfisme de grafs

← Versió més antiga		Revisió del 11:07, 21 maig 2023
Línia 42:		Línia 42:
	===Isomorfisme de grafs===		===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 vertex i arestes

	===Operacions amb grafs===		===Operacions amb grafs===

Mayola: /* Isomorfisme de grafs */

2023-05-21T11:04:43Z

Isomorfisme de grafs

← Versió més antiga		Revisió del 11:04, 21 maig 2023
Línia 41:		Línia 41:

	===Isomorfisme de grafs===		===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===

Mayola: /* Tipus especials de grafs */

2023-05-21T11:03:37Z

Tipus especials de grafs

← Versió més antiga		Revisió del 11:03, 21 maig 2023
Línia 36:		Línia 36:
	:** T<sub>3</sub>		:** T<sub>3</sub>
	::[[Fitxer:ExempleGrafT3.png\|319x319px]]		::[[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===		===Isomorfisme de grafs===

Mayola: /* Tipus especials de grafs */

2023-05-21T10:54:54Z

Tipus especials de grafs

← Versió més antiga		Revisió del 10:54, 21 maig 2023
Línia 27:		Línia 27:
	:**3-regular		:**3-regular
	::[[Fitxer:ExempleGraf3regular.png\|282x282px]]		::[[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.		:* '''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>		:** K <sub>3</sub>
	::[[Fitxer:ExempleGrafK3.png\|310x310px]]		::[[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 ~~una aresta~~ formant un cicle.		:* '''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>		:** C<sub>4</sub>
	::[[Fitxer:ExempleGrafC4.png\|291x291px]]		::[[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]]

	===Isomorfisme de grafs===		===Isomorfisme de grafs===

Mayola: /* Tipus especials de grafs */

2023-05-21T10:47:38Z

Tipus especials de grafs

← Versió més antiga		Revisió del 10:47, 21 maig 2023
Línia 30:		Línia 30:
	:** K <sub>3</sub>		:** K <sub>3</sub>
	::[[Fitxer:ExempleGrafK3.png\|310x310px]]		::[[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 una aresta formant un cicle.
			:** C<sub>4</sub>
			::[[Fitxer:ExempleGrafC4.png\|291x291px]]

	===Isomorfisme de grafs===		===Isomorfisme de grafs===

Mayola: /* Tipus especials de grafs */

2023-05-21T10:43:31Z

Tipus especials de grafs

← Versió més antiga		Revisió del 10:43, 21 maig 2023
Línia 27:		Línia 27:
	:**3-regular		:**3-regular
	::[[Fitxer:ExempleGraf3regular.png\|282x282px]]		::[[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]]

	===Isomorfisme de grafs===		===Isomorfisme de grafs===

Mayola a 10:39, 21 maig 2023

2023-05-21T10:39:47Z

← Versió més antiga		Revisió del 10:39, 21 maig 2023
Línia 6:		Línia 6:
	:**V = {1, 2, 3, 4, 5}		:**V = {1, 2, 3, 4, 5}
	:**A = <nowiki>{{1, 2}, {5, 1}, {5, 4}, {4, 2}, {3, 4}, {3, 5}, {2, 3}}</nowiki>		:**A = <nowiki>{{1, 2}, {5, 1}, {5, 4}, {4, 2}, {3, 4}, {3, 5}, {2, 3}}</nowiki>
	[[Fitxer:ExempleGraf.png\|423x423px]]		::[[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 22:		Línia 22:
	===Tipus especials de grafs===		===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.		:*'''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]]		:**N<sub>4</sub>
			::[[Fitxer:ExempleGrafNul.png\|239x239px]]
	:*'''Graf r-regular'''. Tots els vèrtex amb el mateix grau r		:*'''Graf r-regular'''. Tots els vèrtex amb el mateix grau r
	:**3-regular [[Fitxer:ExempleGraf3regular.png\|282x282px]]		:**3-regular
			::[[Fitxer:ExempleGraf3regular.png\|282x282px]]

	===Isomorfisme de grafs===		===Isomorfisme de grafs===

Mayola: /* Tipus especials de grafs */

2023-05-21T10:39:28Z

Tipus especials de grafs

← Versió més antiga		Revisió del 10:39, 21 maig 2023
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}		:**V = {1, 2, 3, 4, 5}
	::*A = {{1, 2}, {5, 1}, {5, 4}, {4, 2}, {3, 4}, {3, 5}, {2, 3}}		:**A = <nowiki>{{1, 2}, {5, 1}, {5, 4}, {4, 2}, {3, 4}, {3, 5}, {2, 3}}</nowiki>
	[[Fitxer:ExempleGraf.png~~\|center~~\|423x423px]]		[[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>		:** <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>		:** <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.		:**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===

Mayola: /* Propietats */

2023-05-21T10:25:32Z

Propietats

← Versió més antiga		Revisió del 10:25, 21 maig 2023
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 ===