Exercicis de grafs i arbres

La cota.

$|E| \leq 3|V| - 6 = 3\cdot15 - 6 = 39$

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

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, 5, 2, 2, 2]$ 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 $8\cdot4 = 32$, i per tant

$|E| = \frac{32}{2} = 16$

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

$|E| = n - 1 = 14$

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

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

La cota.

$|E| \leq 3|V| - 6 = 3\cdot16 - 6 = 42$

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

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

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 4 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 $8\cdot5 = 40$, i per tant

$|E| = \frac{40}{2} = 20$

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

$|E| = n - 1 = 15$

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

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

La cota.

$|E| \leq 3|V| - 6 = 3\cdot17 - 6 = 45$

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

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.

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 $8\cdot6 = 48$, i per tant

$|E| = \frac{48}{2} = 24$

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.