Resultats de la cerca
Es mostren 24 resultats
graf
(1) Graf orientat: el camí ( a 1, a 2, a 4, a 5) és un circuit , els arcs a 2 i a 3 són bucles o rulls en el vèrtex v 2. i a 6 és un camí de v 1 a v 3. (2) graf no orientat: la cadena ( a 1, a 4, a 5) és un cicle , les arestes a 2 i a 3 són bucles o rulls en el vèrtex v 2, i a 6 és una aresta de v 1 a v 3.
© fototeca.cat
Matemàtiques
Ens constituït per un conjunt S
d’elements i per un conjunt C
de línies que uneixen els elements de S
(tot palesant una correspondència
de S
en si mateix).
Cal distingir entre un graf orientat i un graf no orientat Un graf orientat és una quaterna S, C, o, e , on S és el conjunt d’elements o vèrtexs, C és el conjunt de línies entre els vèrtexs o arcs, o és l' aplicació origen que assigna a cada arc el vèrtex del qual surt, i e és l' aplicació extrem que assigna a cada arc el vèrtex al qual arriba Un graf no orientat és una terna S, C, e , on S és el conjunt dels vèrtexs, C és el conjunt de línies entre els vèrtexs o arestes , i e és l’aplicació que assigna a cada aresta una parella de S × S , formada pels vèrtexs que uneix l’aresta en qüestió…
graf de Petersen
graf de Petersen
Matemàtiques
Graf 3-regular, d’ordre 10, que té diàmetre 2.
A més, és el graf 3-regular de diàmetre 2 amb el nombre més gran de vèrtexs El graf de Petersen és un graf vèrtex-transitiu amb nombre cromàtic 4, que no és de Cayley ni hamiltonià
digraf
digraf
Matemàtiques
Graf les arestes del qual, anomenades arcs, són parells ordenats de vèrtexs diferents.
Un digraf G amb un conjunt de vèrtexs V i un conjunt d’arcs E es denota per G = V , E Sovint s’escriu també E = E G i V = V G
arbre
Tots els arbres amb vuit vèrtexs com a màxim
© fototeca.cat
Matemàtiques
Graf connex i acíclic (sense circuits).
Un arbre té només un vèrtex, anomenat arrel sense predecessor en el sentit de les fletxes, mentre que tot altre vèrtex té, cada un, un únic predecessor Tots els vèrtexs tenen un nombre variable de successors, que ordinariàment hom suposa ordenats per exemple, d’esquerra a dreta i de vegades són anomenats branques En la representació habitual d’un arbre l’arrel se situa al capdamunt i els arcs se suposen recorreguts en sentit descendent Els arbres han passat d’ésser un cas particular de graf a rebre un tractament matemàtic específic Són particularment útils en la modelització de processos en…
aresta-connectivitat
Matemàtiques
Donat un graf G diferent de Kj, nombre mínim d’arestes (representat per ƛ(G) que cal treure del conjunt d’arestes per tal que el graf resultant no sigui connex.
Quan el graf modela una xarxa d’interconnexió, aleshores aquest paràmetre mesura la vulnerabilitat de la xarxa davant la fallada d’enllaços
hipercub
Graf que representa un hipercub unitari de ℝ 4
Fototeca.cat
Matemàtiques
Figura en un espai euclidià de més de tres dimensions que té tots els costats iguals i tots els angles rectes, i que és el producte cartesià de n còpies d’un interval de ℝ.
Per al cas particular de quatre dimensions, l’hipercub és anomenat tesseractis
problema dels set ponts de Königsberg
problema dels set ponts de Königsberg
Fototeca.cat
Matemàtiques
Problema la solució del qual s’associa sovint amb l’origen de la teoria de grafs.
La ciutat prussiana de Königsberg actualment Kaliningrad està dividida pel riu Pregol’a, que voreja l’illa de Kneiphof Hi havia set ponts disposats com s’indica a la figura Els habitants de la ciutat es plantejaven si era possible fer un recorregut tancat que passés una sola vegada per cadascun dels set ponts En llenguatge de teoria de grafs, la pregunta és si el graf és eulerià La resposta és negativa La solució del problema va ser trobada per Leonard Euler, el 1736, introduint per primer cop la noció de graf i resolent a la vegada un problema de caràcter més general
arrel
Matemàtiques
En un arbre, vèrtex caracteritzat pel fet de no haver-hi cap fletxa que s’adreci.
Tot arbre en té una de sola, que s’acostuma a dibuixar al capdamunt del graf