grafos y arboles

Teniendo en cuenta la terminología que se utiliza en teoría de grafos. Identifique la definición correcta de un grafo: A) Un diagrama compuesto de nodos y conexiones. B) Un conjunto de vértices y aristas, tal que cada arista está asociada a un par. C) Múltiples nodos denominados vértices y caminos denominados arcos. D) Un dibujo matemático que se emplea para modelar problemas de la vida real.

Teniendo en cuenta la terminología que se utiliza en teoría de grafos. Identifique la definición correcta de grafo bipartito: ∅, y cada vértice es incidente sobre una artista en E. A) Un grafo G=(V,E) compuesto por subconjuntos de vértices V1 y V2 (cualquiera posiblemente vacío) de V, tal que ????1 ∩ ????2 = ∅, ????1 ∪ ????2 =. B) A) Un grafo G=(V,E) compuesto por subconjuntos de vértices V1 y V2 (cualquiera posiblemente vacío) de V, tal que ????1 ∩ ????2 = ∅,. C) Un grafo G=(V,E) que se puede particionar en dos subconjuntos de vértices V1 y V2 (cualquiera posiblemente vacío) de V, tal que. D) Un grafo que se puede particionar en dos subgrafos no conectados entre sí.

Según la definición estudiada de trayectoria de un grafo. Indique cuál de las opciones es la que mejor define el concepto de trayectoria de un vértice v0 a vn: A) Un camino consecutivo de aristas consecutivas desde v0 a vn. B) es una sucesión de longitud n, alternante de n + 1 vértices y n aristas que comienza en el vértice v0 y termina en el vértice vn,. C) Es un camino de nodos alternantes y consecutivos desde v0 a vn. D) Es un conjunto de n-1 nodos alternantes y consecutivos desde v0 a vn.

Seleccione la opción correcta que demuestre por qué este grafo no es bipartito: A) Porque no posee vértices adyacentes. B) Porque existe una contradicción en cuanto a la pertenencia de los vértices v4, v5, y v6 a los subconjuntos V1 y V2, considerados como la partición del grafo bipartito. C) Porque no se puede separar los vértices contiguos. D) Porque en un grafo completo (fuertemente conexo) no es posible separar a los vértices de manera bipartita.

A partir de los conocimientos adquiridos durante el curso. Elija la opción que mejor defina a un árbol binario. A) Un árbol binario es un árbol con raíz en el que cada vértice tiene ningún hijo, un hijo o dos hijos. B) Un conjunto finito de vértices todos conectados. C) Dos subconjuntos de vértices que se interconectan a través de aristas externas e incidentes solo en estos conjuntos. D) Un conjunto infinito de vértices todos conectados.

A partir de las definiciones conocidas de árbol. Determine que opción se ajusta más a la definición correcta de árbol. A) es una estructura de datos en la informática. B) Un árbol T (libre) es un grafo simple que satisface lo siguiente: si v y w son vértices en T, existe una trayectoria simple única de v a w. C) Es un cojunto de vértices y aristas que insiden entren sí para formar un modelo con forma arbórea. D) Es un ciclo hamiltoniano y a la vez de Euler.

Un ciclo de Euler es una trayectoria en la que el vértice de inicio y fin es el mismo, sin aristas repetidas, y donde se incluyen todas las aristas y vértices del grafo. Considere el siguiente grafo. Seleccione la opción correcta que explique por qué dicho grafo no contiene un ciclo de Euler. A) Porque el grafo contiene un número impar de vértices. B) Porque el grado de todos los vértices es un número par. C) Porque el grado de todos los vértices es un número impar. D) Porque el grado de todos los vértices es un número primo.

En honor a Hamilton, un ciclo en un grafo G que contiene cada vértice en G justo una vez, excepto por el vértice inicial y final que aparece dos veces, recibe el nombre de ciclo hamiltoniano. Considere el siguiente grafo. Seleccione la opción que justifique de manera más completa, por qué no contiene un ciclo hamiltoniano. A) Porque el vértice v5 está conectado a v2 y v4, y no a v1. B) Existe un único camino de v4 a v2, y el número de vértices es impar. C) Porque se debe garantizar 5 aristas en total, siendo el grado de cada vértice un número par, y al eliminar cualquiera de las incidentes en los vértices v2 y v4, entonces v1, v3, o v5 se quedan con solo una arista. D) Porque se debe garantizar 5 aristas en total, siendo el grado de cada vértice un número impar, y al eliminar cualquiera de las incidentes en el vértice v5, entonces v2 se queda con solo dos aristas.

Sea un grafo T de n vértices. Determine que opción resulta equivalente a la definición de árbol. A) T es conexo y con ciclos. B) T es conexo con n-1 aristas. C) T es acíclico y contiene n aristas. D) T es acíclico y contiene n-1 aristas.

Seleccione la opción que argumente por qué el grafo formado por las aristas de líneas sólidas constituye un árbol de expansión. A)Porque se trata de un subgrafo de G que contiene a todos los vértices de G. B) Porque se trata de un grafo no conexo. C) Porque se trata de un grafo conexo acíclico que contiene a todos los vértices del grafo G. D) Porque se trata de un grafo no cíclico.