Teoría de grafos

Conceptos

• Grafo 10 ejerciciosUn grafo G es un conjunto V de vértices junto con un conjunto E de aristas, cada una formada por dos vértices distintos.
• Grado de un vértice 10 ejerciciosEl grado deg(v) de un vértice v es el número de aristas del grafo (el conjunto E) que lo tienen como extremo.
• Camino en un grafo 10 ejerciciosUn camino de longitud k es una sucesión de vértices v_0,dots,v_k tal que cada par consecutivo está unido por una arista de E.
• Grafo conexo 10 ejerciciosUn grafo G=(V,E) es conexo si cualesquiera dos vértices u,v∈ V están unidos por un camino.
• Árbol 10 ejerciciosUn árbol T=(V,E) es un grafo conexo que no contiene ciclos.
• Ciclo euleriano 10 ejerciciosUn ciclo euleriano de un grafo G=(V,E) es un ciclo que recorre cada arista de G exactamente una vez.
• Ciclo hamiltoniano 10 ejerciciosUn ciclo hamiltoniano de un grafo G con n≥ 3 vértices es un ciclo que pasa por cada vértice de G exactamente una vez.
• Grafo bipartito 10 ejerciciosUn grafo bipartito es un grafo G=(V,E) cuyos vértices se reparten en dos conjuntos disjuntos A y B de modo que cada arista e∈ E u…
• Coloración de grafos 10 ejerciciosUna coloración propia c con k colores de un grafo G=(V,E) asigna a cada vértice uno de los colores 1,dots,k sin que dos vértices…
• Grafo planar 10 ejerciciosUn grafo planar es un grafo que admite un dibujo en el plano sin cruces de aristas; ese dibujo, para v vértices y e aristas, divi…