Grafs Ll1

Aquesta secció introdueix el concepte de graf per millorar la percepció i la connexió entre conceptes a l'hora de tancar problemes d'estratègia. És un tema molt aplicat en el pensament computacional i la lògica proposicional.

Grafs

Un $grafG(V,A)$ és una construcció on $V=\{v_{1},v_{2},\dots ,v_{i},\dots \}$ és un conjunt de punts o vèrtex, i $A=\{a_{1},a_{2},\dots ,a_{j},\dots \}$ són línies entre punts de V.

Si les línies estan orientades direm que és un graf dirigit i les línies es diuen arcs.

Si les línies no estan orientades direm que és un graf simètric i les línies es diuen arestes.

Observació

• Si escrivim $v_{i+3}$ i $V=\{v_{1},v_{2},v_{3},v_{4},v_{5}\}$ llavors només es referirà als valors de i tals que $i+3\leq 5$ i el conjunt de punts també es pot escriure com $V=\{v_{i}|i\in I=\{1,2,3,4,5\}\}=\{v_{i}|i\in \mathbb {N} ,1\leq i\leq 5\}$

Exemples a explicar o proposar

1)	Construeix el graf dirigit on $V=\{v_{1},v_{2},v_{3},v_{4}\}$ i $A=\{a_{1}=(v_{1},v_{2}),a_{2}=(v_{1},v_{3}),a_{3}=(v_{3},v_{1}),a_{4}=(v_{2},v_{3}),a_{5}=(v_{4},v_{4})\}$
2)	Construeix el graf simètric on $V=\{v_{1},v_{2},v_{3},v_{4},v_{5}\}$ i $A=\{a_{1}=(v_{1},v_{2}),a_{2}=(v_{2},v_{3}),a_{3}=(v_{3},v_{4}),a_{4}=(v_{4},v_{5}),a_{5}=(v_{5},v_{1})\}$
3)	Construeix el graf simètric determinat de manera que els punts són $V=\{v_{i}|\;i\in I=\{1,2,3,4,5,6\}\;\}$ i les arestes $A=\{(v_{i},v_{i+1}),(v_{i},v_{i+2})\}$ sempre que tinguin sentit o sigui i+1 està dins dels valors I o i+2 està dins dels valors I Quantes arestes té? Es pot dibuixar sense que es creuin les arestes?
4)	Calcula les arestes que té el graf simètric determinat per $V=\{v_{1},v_{2},\dots ,v_{n}\}$ i $A=\{(v_{i},v_{i+1}),(v_{n},v_{1})\}$ segons els diferents valors que pot prendre n.
5)	Calcula les arestes que té el graf simètric determinat per $V=\{v_{1},v_{2},\dots ,v_{n}\}$ on hi ha totes les possibles arestes entre els vèrtex.

Repte 1

Solutio problematis pontium Regiomontii

Por Leonhard Euler.

Consisteix en creuar per sobre de tots els ponts de la ciutat sense passar dos cops pel mateix pont, els ponts(verd) uneixen diferents parts de la ciutat dividida pel riu(blau cel) en diverses parts.

Repte 2

La reunió

Lèxic

• Vèrtex i punts
• Grafs dirigits

• Arc

• Grafs simètrics

• Arestes

Conceptes claus

• Connexions a la realitat
• Adaptació de problemes
• Abstracció de problemes
• Construcció de la cerca de solucions segons

• La veracitat
• La quantitat de solucions

• Llibertat de solucions
• Concreció de solucions

• Construcció i examen de conjectures

• Fórmules explícites
• Fórmules implícites
• Fórmules iteratives

• Familiarització amb notacions:

• Superíndex i subíndex
• Successions amb terme general
• Conjunts
• Elements
• Condicions o restriccions
• Relació entre conjunts
• Arbres analítics de possibilitats o estructura

• Connexions o reforç amb futures eines o conceptes

• Vectors
• Matrius
• Sumatoris
• Autòmats

• Diagrames de flux
• Iteració