Exercicis de grafs i arbres

El lema de les encaixades.

$\sum_{v} d(v) = 2|E|$

perquè cada aresta aporta $1$ al grau de cadascun dels seus dos extrems.

Aquí: la suma de graus és $4\cdot2 = 8$, i per tant

$|E| = \frac{8}{2} = 4$

La comprovació de paritat. La suma de graus sempre és parella. Si un enunciat et dona graus que sumen senar, aquell graf no existeix i no cal intentar dibuixar-lo. És una de les maneres més ràpides de descartar configuracions impossibles.

El resultat. Un arbre amb $2$ vèrtexs té exactament

$|E| = n - 1 = 1$

arestes.

Per què. Comença amb un sol vèrtex i cap aresta. Cada vegada que afegeixes un vèrtex nou l'has de connectar amb exactament una aresta: amb cap quedaria aïllat, i amb dues o més tancaries un cicle. Per tant, $2$ vèrtexs necessiten $1$ arestes.

Les dues cares del resultat. Connectar $2$ vèrtexs necessita com a mínim $1$ arestes; i un graf amb $2$ arestes o més sobre $2$ vèrtexs ha de tenir algun cicle. L'arbre és exactament el cas frontera.

La cota.

$|E| \leq 3|V| - 6 = 3\cdot3 - 6 = 3$

D'on surt. De la fórmula d'Euler $|V| - |E| + |F| = 2$ i del fet que, en un graf simple, cada cara està limitada per almenys $3$ arestes i cada aresta toca com a molt $2$ cares. Això dona $2|E| \geq 3|F|$, i substituint a Euler surt la desigualtat.

Si a més el graf és bipartit, no hi pot haver cicles de longitud $3$ i cada cara necessita almenys $4$ arestes; la cota baixa a $2|V| - 4 = 2$.

Molt important: aquestes cotes són necessàries, no suficients. Si un graf les incompleix segur que no és planar; si les compleix, encara podria no ser-ho.

Pas 1 — comptar els graus senars. Als graus $[2, 2, 2, 2]$ n'hi ha 0.

Pas 2 — aplicar el criteri. En un graf connex:

• Zero vèrtexs de grau senar: hi ha circuit eulerià, que torna al punt de partida.
• Exactament dos: hi ha recorregut obert, i ha de començar en un d'ells i acabar a l'altre.
• Més de dos: no hi ha cap recorregut que faci totes les arestes d'una tirada.

Amb 0 senars, la resposta és Circuit eulerià tancat.

Per què funciona. Cada vegada que passes per un vèrtex intermedi hi entres i en surts, o sigui que consumeixes dues arestes. Només els extrems del recorregut poden quedar descompensats, i n'hi ha com a molt dos.

El lema de les encaixades.

$\sum_{v} d(v) = 2|E|$

perquè cada aresta aporta $1$ al grau de cadascun dels seus dos extrems.

Aquí: la suma de graus és $4\cdot3 = 12$, i per tant

$|E| = \frac{12}{2} = 6$

La comprovació de paritat. La suma de graus sempre és parella. Si un enunciat et dona graus que sumen senar, aquell graf no existeix i no cal intentar dibuixar-lo. És una de les maneres més ràpides de descartar configuracions impossibles.

El resultat. Un arbre amb $3$ vèrtexs té exactament

$|E| = n - 1 = 2$

arestes.

Per què. Comença amb un sol vèrtex i cap aresta. Cada vegada que afegeixes un vèrtex nou l'has de connectar amb exactament una aresta: amb cap quedaria aïllat, i amb dues o més tancaries un cicle. Per tant, $3$ vèrtexs necessiten $2$ arestes.

Les dues cares del resultat. Connectar $3$ vèrtexs necessita com a mínim $2$ arestes; i un graf amb $3$ arestes o més sobre $3$ vèrtexs ha de tenir algun cicle. L'arbre és exactament el cas frontera.

La cota.

$|E| \leq 3|V| - 6 = 3\cdot4 - 6 = 6$

D'on surt. De la fórmula d'Euler $|V| - |E| + |F| = 2$ i del fet que, en un graf simple, cada cara està limitada per almenys $3$ arestes i cada aresta toca com a molt $2$ cares. Això dona $2|E| \geq 3|F|$, i substituint a Euler surt la desigualtat.

Si a més el graf és bipartit, no hi pot haver cicles de longitud $3$ i cada cara necessita almenys $4$ arestes; la cota baixa a $2|V| - 4 = 4$.

Molt important: aquestes cotes són necessàries, no suficients. Si un graf les incompleix segur que no és planar; si les compleix, encara podria no ser-ho.

Pas 1 — comptar els graus senars. Als graus $[2, 2, 3, 3]$ n'hi ha 2.

Pas 2 — aplicar el criteri. En un graf connex:

• Zero vèrtexs de grau senar: hi ha circuit eulerià, que torna al punt de partida.
• Exactament dos: hi ha recorregut obert, i ha de començar en un d'ells i acabar a l'altre.
• Més de dos: no hi ha cap recorregut que faci totes les arestes d'una tirada.

Amb 2 senars, la resposta és Recorregut eulerià obert.

Per què funciona. Cada vegada que passes per un vèrtex intermedi hi entres i en surts, o sigui que consumeixes dues arestes. Només els extrems del recorregut poden quedar descompensats, i n'hi ha com a molt dos.

El lema de les encaixades.

$\sum_{v} d(v) = 2|E|$

perquè cada aresta aporta $1$ al grau de cadascun dels seus dos extrems.

Aquí: la suma de graus és $5\cdot2 = 10$, i per tant

$|E| = \frac{10}{2} = 5$

La comprovació de paritat. La suma de graus sempre és parella. Si un enunciat et dona graus que sumen senar, aquell graf no existeix i no cal intentar dibuixar-lo. És una de les maneres més ràpides de descartar configuracions impossibles.

El resultat. Un arbre amb $4$ vèrtexs té exactament

$|E| = n - 1 = 3$

arestes.

Per què. Comença amb un sol vèrtex i cap aresta. Cada vegada que afegeixes un vèrtex nou l'has de connectar amb exactament una aresta: amb cap quedaria aïllat, i amb dues o més tancaries un cicle. Per tant, $4$ vèrtexs necessiten $3$ arestes.

Les dues cares del resultat. Connectar $4$ vèrtexs necessita com a mínim $3$ arestes; i un graf amb $4$ arestes o més sobre $4$ vèrtexs ha de tenir algun cicle. L'arbre és exactament el cas frontera.