Exercicis de grafs i arbres

La cota.

$|E| \leq 3|V| - 6 = 3\cdot10 - 6 = 24$

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 = 16$.

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, 4, 6, 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 $7\cdot2 = 14$, i per tant

$|E| = \frac{14}{2} = 7$

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 $10$ vèrtexs té exactament

$|E| = n - 1 = 9$

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, $10$ vèrtexs necessiten $9$ arestes.

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

La cota.

$|E| \leq 3|V| - 6 = 3\cdot11 - 6 = 27$

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 = 18$.

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 $[3, 3, 3, 3, 3, 3]$ n'hi ha 6.

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 6 senars, la resposta és Cap de les dues.

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 $7\cdot4 = 28$, i per tant

$|E| = \frac{28}{2} = 14$

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 $11$ vèrtexs té exactament

$|E| = n - 1 = 10$

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, $11$ vèrtexs necessiten $10$ arestes.

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

La cota.

$|E| \leq 3|V| - 6 = 3\cdot12 - 6 = 30$

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 = 20$.

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]$ 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.