Taula de continguts
58 les relacions: Algorisme de Dijkstra, Algorisme de Ford-Fulkerson, Algorisme de Prim, Aparellament (teoria de grafs), Arbre (teoria de grafs), Arbre de joc, Aresta (geometria), Aresta (teoria de grafs), Arestes múltiples, Aualé, Autòmat finit acíclic determinista, Bucle (teoria de grafs), Camí (teoria de grafs), Camí eulerià, Camí hamiltonià, Categoria (matemàtiques), Cerca en amplada, Coloració de grafs, Component fortament connex, Connectivitat-st, Diagrama de Coxeter-Dynkin, Diagrama de Schlegel, Distància (teoria de grafs), Distribució de grau, Doble factorial, Els set ponts de Königsberg, Graf (matemàtiques), Graf acíclic dirigit, Graf bipartit, Graf complet, Graf de Dyck, Graf de Petersen, Graf dual, Graf nul, Graf pla, Grau (teoria de grafs), Grup lliure, Hipergraf, K-mer, L (complexitat), Lema de Berge, Lema de l'encaixada de mans, Matriu d'incidència, Mètode de percolació de cliques, Model de blocs, Nombre surreal, Objecte matemàtic, Problema de Hadwiger–Nelson, Problema del camí més llarg, Teorema de Kirchhoff, ... Ampliar l'índex (8 més) »
Algorisme de Dijkstra
Execució de l'algorisme de Dijkstra L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme de cerca de camins per determinar el camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta.
Veure Vèrtex (teoria de grafs) і Algorisme de Dijkstra
Algorisme de Ford-Fulkerson
L'algorisme de Ford-Fulkerson és un algorisme que calcula el flux màxim en una xarxa de flux.
Veure Vèrtex (teoria de grafs) і Algorisme de Ford-Fulkerson
Algorisme de Prim
En teoria de grafs, l'algorisme de Prim és un algorisme que serveix per trobar un arbre generador minimal en un graf connex, no dirigit i amb arestes etiquetades.
Veure Vèrtex (teoria de grafs) і Algorisme de Prim
Aparellament (teoria de grafs)
Un aparellament d'un graf, representat en vermell En la disciplina matemàtica de la teoria de grafs, un aparellament d'un graf és un conjunt d'arestes sense vèrtexs en comú.
Veure Vèrtex (teoria de grafs) і Aparellament (teoria de grafs)
Arbre (teoria de grafs)
En teoria de grafs, un arbre és un graf en el qual dos vèrtexs estan connectats per exactament un camí.
Veure Vèrtex (teoria de grafs) і Arbre (teoria de grafs)
Arbre de joc
Arbre de joc sencer del tic-tac-toe. Un arbre de joc és un gràfic que representa tots els estats de joc possibles dins d’aquest joc, això en el context de la teoria de joc combinatòria, que normalment estudia jocs seqüencials amb informació perfecta.
Veure Vèrtex (teoria de grafs) і Arbre de joc
Aresta (geometria)
vèrtexs. En geometria, una aresta és un segment lineal de dimensió 1 que uneix dos vèrtexs de dimensió zero en un polígon, un políedre, o més en general un polítop.
Veure Vèrtex (teoria de grafs) і Aresta (geometria)
Aresta (teoria de grafs)
Alguns exemples d'arestes, orientades i no orientades: a) Aresta no orientada; b) Aresta orientada; c) Cicle orientat; d) Multiarestes, una d'orientada i l'altra no; e) Multiarestes no orientades; f) Multiarestes orientades; g) Bucle orientat; h) Bucle no orientat; i) Multibucle orientat; j) Multibucle no orientat En teoria de grafs, una aresta correspon a una relació entre dos vèrtexs d'un graf.
Veure Vèrtex (teoria de grafs) і Aresta (teoria de grafs)
Arestes múltiples
graf admet arestes múltiples, es diu multigraf En matemàtiques, i més concretament en teoria de grafs, les arestes múltiples (també anomenades arestes paral·leles o una multiaresta) són dues o més arestes que són incidents (és a dir, que connecten) a almenys dos vèrtexs.
Veure Vèrtex (teoria de grafs) і Arestes múltiples
Aualé
L'aualé és un joc amb adversari que es juga amb quaranta-vuit fitxes, anomenades llavors, en un tauler rectangular format per dues fileres de sis forats cadascuna.
Veure Vèrtex (teoria de grafs) і Aualé
Autòmat finit acíclic determinista
Un autòmat finit acíclic determinista és un tipus d'autòmat finit (en anglès deterministic acyclic finite state automaton, DAFSA) és una estructura de dades que representa un conjunt de cadenes de caràcters i permet operacions de cerca i qüestions sobre si una cadena donada pertany al conjunt en un temps proporcional a la seva longitud.
Veure Vèrtex (teoria de grafs) і Autòmat finit acíclic determinista
Bucle (teoria de grafs)
Un graf amb un bucle en el vèrtex 1. En teoria de grafs, un bucle o loop és una aresta que connecta un vèrtex amb si mateix.
Veure Vèrtex (teoria de grafs) і Bucle (teoria de grafs)
Camí (teoria de grafs)
negre gruixut) En teoria de grafs, un camí o ruta és una seqüència de vèrtexs dins d'un graf tal que hi ha una aresta entre cada vèrtex i el següent.
Veure Vèrtex (teoria de grafs) і Camí (teoria de grafs)
Camí eulerià
Un camí o cicle eulerià és aquell camí que recorre tots els vèrtexs (nodes) d'un graf passant una i només una vegada per cada arc (aresta) del graf, i és condició necessària que torni al vèrtex inicial de sortida (camí.
Veure Vèrtex (teoria de grafs) і Camí eulerià
Camí hamiltonià
Un camí hamiltonià (en negre) sobre un graf (en blau). En el camp matemàtic de la teoria de grafs, un camí hamiltonià és un camí en un graf no dirigit que passa per cada vèrtex del graf exactament un cop.
Veure Vèrtex (teoria de grafs) і Camí hamiltonià
Categoria (matemàtiques)
''g'' ∘ ''f'', i els bucles són les fletxes de les respectives aplicacions identitat. Aquesta categoria s'acostuma a denotar per un '''3''' en negreta. En matemàtiques, una categoria (de vegades anomenada categoria abstracta per distingir-la d'una categoria concreta) és una col·lecció d'"objectes" que s'enllacen mitjançant "fletxes".
Veure Vèrtex (teoria de grafs) і Categoria (matemàtiques)
Cerca en amplada
La cerca en amplada (de l'anglès BFS - Breadth First Search) és un algorisme informàtic per recórrer o buscar elements en un graf (usat sovint en arbres).
Veure Vèrtex (teoria de grafs) і Cerca en amplada
Coloració de grafs
Una coloració adequada del graf de Petersen amb 3 colors, el mínim nombre possible perquè no n'hi hagi dos de contigus. En teoria de grafs, la coloració de grafs és un cas especial d'etiquetatge de grafs, una assignació d'etiquetes tradicionalment anomenades «colors» als elements d'un graf subjecte a certes restriccions.
Veure Vèrtex (teoria de grafs) і Coloració de grafs
Component fortament connex
Un graf dirigit, i els seus components fortament connexos. En teoria de grafs, un graf dirigit és fortament connex si per a cada parell de vèrtexs u i v hi ha un camí de u cap a v i un camí de v cap a u. Els components fortament connexos (CFC) d'un graf dirigit són els seus subgrafs màxims fortament connexos.
Veure Vèrtex (teoria de grafs) і Component fortament connex
Connectivitat-st
En teoria de la complexitat, el problema de connectivitat-st o STCON (pel nom en anglès st-connectivity) és un problema de decisió tal que donat un graf dirigit, cal saber si un vèrtex t és accessible des de s. Formalment, el problema es descriu així:CAMÍ.
Veure Vèrtex (teoria de grafs) і Connectivitat-st
Diagrama de Coxeter-Dynkin
Diagrames de Coxeter-Dynkin per als grups de Coxeter finits fonamentals Diagrames de Coxeter-Dynkin per als grups de Coxeter afins fonamentals En geometria, un diagrama de Coxeter-Dynkin (diagrama de Coxeter, o graf de Coxeter), nomenat així pels matemàtics Donald Coxeter i Eugene Dynkin, és un graf amb arestes etiquetades numèricament (anomenades «branques») que representen les relacions espacials entre una col·lecció de miralls (o hiperplans reflectits).
Veure Vèrtex (teoria de grafs) і Diagrama de Coxeter-Dynkin
Diagrama de Schlegel
Diagrama de Schlegel d'un octaedre regular compost de vuit cares, cada una de les quals és un triangle equilàter. Tal com s'aprecia al diagrama, cada vèrtex veu quatre cares (la part exterior també compta com a cara). Un diagrama de Schlegel és un graf planar que representa l'esquelet polièdric d'una figura geomètrica de tres o més dimensions.
Veure Vèrtex (teoria de grafs) і Diagrama de Schlegel
Distància (teoria de grafs)
En teoria de grafs, la distància entre els dos vèrtexs d'un graf és el nombre d'arestes en el camí més curt que els uneix.
Veure Vèrtex (teoria de grafs) і Distància (teoria de grafs)
Distribució de grau
Comparació entre dues distribucions de grau en xarxes lliures d'escala i xarxes aleatòries. En l'estudi de grafs i xarxes complexes, el grau d'un vèrtex en una xarxa és el nombre de connexions associades a un vèrtex.
Veure Vèrtex (teoria de grafs) і Distribució de grau
Doble factorial
vèrtexs. Aquests són comptats pel doble factorial 15.
Veure Vèrtex (teoria de grafs) і Doble factorial
Els set ponts de Königsberg
Mapa de Königsberg mostrant la disposició dels set ponts sobre el riu Pregolya. Els set ponts de Königsberg és un famós problema matemàtic que va donar origen a la teoria de grafs.
Veure Vèrtex (teoria de grafs) і Els set ponts de Königsberg
Graf (matemàtiques)
Representació d'un graf etiquetat, amb 6 vèrtexs i set arestes En teoria de grafs, un graf és una representació abstracta d'un conjunt d'objectes on alguns parells dels objectes estan connectats per enllaços.
Veure Vèrtex (teoria de grafs) і Graf (matemàtiques)
Graf acíclic dirigit
Un DAG simple. En ciències de la computació i matemàtiques un graf acíclic dirigit (o grafo acíclic dirigit) conegut com a DAG per les seves sigles en anglès, és un graf dirigit que no té cicles; això significa que per a cada vèrtex v, no hi ha un camí directe que comenci i acabi en v.
Veure Vèrtex (teoria de grafs) і Graf acíclic dirigit
Graf bipartit
Exemple de graf bipartit. Un graf bipartit és en teoria de grafs un graf no dirigit els vèrtexs del qual es poden separar en dos conjunts disjunts V_1 i V_2 i les arestes sempre uneixen vèrtexs d'un conjunt amb vèrtexs d'un altre: Sent V el conjunt que conté tots els vèrtexs del graf.
Veure Vèrtex (teoria de grafs) і Graf bipartit
Graf complet
En el camp matemàtic de la teoria de grafs, un graf complet és un graf simple on una aresta connecta tots els parells de vèrtexs.
Veure Vèrtex (teoria de grafs) і Graf complet
Graf de Dyck
En matemàtiques, i més concretament en teoria de grafs, un graf de Dyck és un graf 3-regular no dirigit amb 32 vèrtexs i 48 arestes.
Veure Vèrtex (teoria de grafs) і Graf de Dyck
Graf de Petersen
pentàgon amb un pentacle a l'interior. En l'àmbit matemàtic de la teoria de grafs, el graf de Petersen és un graf no dirigit amb 10 vèrtexs i 15 arestes.
Veure Vèrtex (teoria de grafs) і Graf de Petersen
Graf dual
El graf G és dual del G ', i viceversa A teoria de grafs, un graf dual (G) d'un graf planar G és un graf que té un vèrtex per a cada regió de G, i una aresta per cada aresta en G unint a dues regions veïnes.
Veure Vèrtex (teoria de grafs) і Graf dual
Graf nul
En teoria de grafs, el graf nul és un graf trivial que no té ni vèrtexs ni arestes.
Veure Vèrtex (teoria de grafs) і Graf nul
Graf pla
En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla).
Veure Vèrtex (teoria de grafs) і Graf pla
Grau (teoria de grafs)
Un graf amb vèrtexs etiquetats segons el seu grau. El ''vèrtex aïllat'' s'etiqueta amb 0, ja que no és adjacent a cap altre vèrtex. En teoria de grafs, el grau o valència d'un vèrtex és el nombre d'arestes que hi incideixen, amb els bucles comptats dues vegades.
Veure Vèrtex (teoria de grafs) і Grau (teoria de grafs)
Grup lliure
aresta representa la multiplicació per ''a'' o per ''b''. En matemàtiques, el grup lliure FS sobre un conjunt donat S consisteix en totes les expressions (també conegudes com a paraules o termes) que es poden construir a partir dels elements de S, considerant que dues expressions són diferents llevat que la seva igualtat sigui una conseqüència dels axiomes de grup (per exemple,.
Veure Vèrtex (teoria de grafs) і Grup lliure
Hipergraf
Exemple d'un hipergraf, en el qual V.
Veure Vèrtex (teoria de grafs) і Hipergraf
K-mer
El terme k-mer fa referència a totes les subcadenes possibles de longitud k contingudes en una cadena.
Veure Vèrtex (teoria de grafs) і K-mer
L (complexitat)
En teoria de la complexitat, la classe de complexitat L, també coneguda com a LSPACE o DLOGSPACE, és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing determinista usant una quantitat logarítmica d'espai.
Veure Vèrtex (teoria de grafs) і L (complexitat)
Lema de Berge
En teoria de grafs, el lema de Berge és un lema demostrat pel matemàtic francès Claude Berge el 1957, que diu el següent: Un aparellament és màxim si conté el major nombre d'arestes possibles.
Veure Vèrtex (teoria de grafs) і Lema de Berge
Lema de l'encaixada de mans
En aquest graf, un nombre parell de vèrtexs (els quatre enumerats amb 2, 4, 5 i 6) tenen graus senars. La suma dels graus dels vèrtexs és 2 + 3 + 2 + 3 + 3 + 1.
Veure Vèrtex (teoria de grafs) і Lema de l'encaixada de mans
Matriu d'incidència
En matemàtiques, una matriu d'incidència és una matriu que mostra la relació entre dues classes d'objectes.
Veure Vèrtex (teoria de grafs) і Matriu d'incidència
Mètode de percolació de cliques
El Mètode de Percolació de cliques (conegut com a CPM, de l'anglès Clique percolation method) és el mètode més utilitzat per l'anàlisi de superposició de l'estructura comunitària de les xarxes.
Veure Vèrtex (teoria de grafs) і Mètode de percolació de cliques
Model de blocs
Diferents característiques de les xarxes socials. A, B i C mostren una centralitat i densitat variables de xarxes; El panel D mostra el tancament de la xarxa, és a dir, quan dos actors, lligats a un tercer actor comú, també tendeixen a formar un vincle directe entre ells. El panell E representa dos actors amb atributs diferents (per exemple, afiliació organitzativa, creences, gènere, educació) que tendeixen a formar vincles.
Veure Vèrtex (teoria de grafs) і Model de blocs
Nombre surreal
En matemàtiques, el sistema de nombres surreals és una classe pròpia totalment ordenada que conté els nombres reals, així com nombres infinits i infinitesimals, més grans o més petits respectivament en valor absolut que qualsevol nombre real positiu.
Veure Vèrtex (teoria de grafs) і Nombre surreal
Objecte matemàtic
Un objecte matemàtic és un objecte abstracte que apareix en la filosofia de les matemàtiques i en les matemàtiques.
Veure Vèrtex (teoria de grafs) і Objecte matemàtic
Problema de Hadwiger–Nelson
Pla amb hexàgons de 7 colors, i un graf de distància unitària al pla (el graf de Moser), demostrant que el nombre cromàtic està fitat entre 4 i 7. En teoria de grafs, el problema de Hadwiger–Nelson, anomenat així per Hugo Hadwiger i Edward Nelson, demana el nombre mínim de colors necessari per acolorir el pla de manera que no hi hagi dos punts a la distància 1 l'un de l'altre que tinguin el mateix color.
Veure Vèrtex (teoria de grafs) і Problema de Hadwiger–Nelson
Problema del camí més llarg
En teoria de grafs i ciència computacional teòrica, el problema del camí més llarg és el problema de trobar un camí simple de màxima longitud possible en un determinat graf.
Veure Vèrtex (teoria de grafs) і Problema del camí més llarg
Teorema de Kirchhoff
En matemàtiques, i més concretament en teoria de grafs, el teorema de Kirchhoff, anomenat en referència a Gustav Kirchhoff, és un teorema sobre el nombre d'arbres d'expansió en un gràf, i mostra que aquest nombre es pot calcular en temps polinòmic com el determinant d'una matriu derivada del graf.
Veure Vèrtex (teoria de grafs) і Teorema de Kirchhoff
Teorema de l'amistat
grafs possibles d'amics-estranys amb 6 vèrtexs. A cada graf, les arestes de color blau/vermell mostren la relació mútua d'amics/estranys. El teorema d'amics i estranys o teorema de l'amistat és un teorema en el camp matemàtic anomenat teoria de Ramsey.
Veure Vèrtex (teoria de grafs) і Teorema de l'amistat
Teorema dels quatre colors
Exemple d'un mapa de quatre colors. Mapa del món acolorit de color verd, taronja, blau i porpra. Un mapa de quatre colors dels estats dels Estats Units (sense tenir en compte els llacs). Mapa administratiu de Rússia acolorit amb quatre colors En matemàtiques, el teorema dels quatre colors estableix que en qualsevol partició d'un pla en regions contigües, que produeix una figura anomenada mapa, no es necessiten més de quatre colors per a acolorir les regions del mapa de manera que no hi hagi dues regions adjacents del mateix color.
Veure Vèrtex (teoria de grafs) і Teorema dels quatre colors
Teoria de grafs
La teoria de grafs és una branca de les matemàtiques i la informàtica que es dedica a l'estudi dels grafs, estructures matemàtiques utilitzades per a modelitzar relacions entre parelles d'objectes.
Veure Vèrtex (teoria de grafs) і Teoria de grafs
Test de planaritat
En teoria de grafs, el test de planaritat és un problema que consisteix en demostrar si un graf és pla, és a dir, si pot ser dibuixat a un pla sense que hi hagi interseccions entre les arestes.
Veure Vèrtex (teoria de grafs) і Test de planaritat
Tetràedre
Un tetràedre o tetraedre (ambdues variants són acceptades) és un políedre que té quatre cares.
Veure Vèrtex (teoria de grafs) і Tetràedre
Vèrtex
* Vèrtex (geometria), punt comú entre dos costats consecutius d'una figura geomètrica.
Veure Vèrtex (teoria de grafs) і Vèrtex
Vèrtex (geometria)
Representació d'un octaedre en el que els '''vèrtexs''' estan marcats amb una esfera Un vèrtex és, en geometria, un punt comú entre dos costats consecutius d'una figura geomètrica.
Veure Vèrtex (teoria de grafs) і Vèrtex (geometria)
Veïnat (teoria de grafs)
Un graf format per 6 vèrtexs i 7 arestes. En teoria de grafs, el veïnat d'un vèrtex v en un graf G és el subgraf induït de G format per tots els vèrtexs adjacents de v (és a dir, vèrtexs connectats a v per una aresta) i per totes les arestes que connecten dos d'aquests vèrtexs.
Veure Vèrtex (teoria de grafs) і Veïnat (teoria de grafs)
També conegut com Vèrtex aïllat.