Gráficos conectados, sin bucles y Multigraphs transitables
bdvg2302
Me gustaría saber si estoy en lo cierto con estos ejercicios.
1. ¿Cuáles de los siguientes gráficos son?
a. Conectado: 1º, 3º
Descarto el segundo porque aunque hay dos arcos que se intersecan, leí que esto no significa que haya un vértice en la intersección, así que asumo que el arco que interseca al triángulo no está conectado porque no puedo. t llegar de uno de esos vértices a uno en el triángulo. Por la misma razón y descartando el 4to. Avísame si me equivoco.
b. Libre de bucles: 1º, 2º, 3º
C. Gráficos: 1º, 2º
Descarto el tercero y el cuarto porque son multigrafos.
2. ¿Cuál de los multigrafos es transitable?
Los multigrafos que son transitables son el 1º, 3º y 4º.
Respuestas (1)
Tomás Lesgourgues
En resumen, tiene razón para 1a, 1b, 1c . Tenga en cuenta que para la pregunta 1c preferimos decir gráfico simple en oposición a multigrafo . De hecho, un multigrafo sigue siendo una especie de gráfico.
No puedo decir con seguridad para 2 ya que carece de la definición de transitable. Supongo que significa que el gráfico tiene una ruta de Euler: un camino que visita cada borde exactamente una vez (lo que permite volver a visitar los vértices). Se sabe que un grafo conexo tiene un camino de Euler si y solo si el número de vértices con grado impar es exactamente 2 o 0. Por lo tanto, tu respuesta para la pregunta 2 también sería correcta.
Para la pregunta 1.a. , si quieres entender por qué dos aristas no se cruzan en un vértice: hay una diferencia crucial entre un gráfico y el dibujo de un gráfico. Un gráfico se define sin el uso de dibujo. Es un conjunto de elementos (llamados vértices), junto con un conjunto de pares de elementos (las aristas). Al mirar un dibujo de un gráfico, puede mover libremente cualquier vértice o doblar un borde tanto como desee. Los diferentes dibujos que obtendrás siempre representarán el mismo gráfico. Veamos tu segundo ejemplo. Tenemos un grafo definido en 5 vértices, podemos etiquetarlos y cuatro aristas .
Esto significa que puede mover el vértice y obtener el siguiente dibujo:
Este dibujo es claramente de un gráfico de desconexión. Por lo tanto, este será el caso para cualquier dibujo de este mismo gráfico, incluso si pones uno más complejo como:
Este es el mismo gráfico. Dibujos diferentes pero de la misma gráfica porque los vértices y las aristas son iguales.
Para un dibujo dado, cuando dos bordes se cruzan (no un vértice), esto en realidad se llama cruce. Después de eso, podemos ver algunas preguntas relacionadas, principalmente: Para un gráfico dado, ¿cuál es el menor número posible de cruces en cualquier dibujo de este gráfico? Si puede encontrar un dibujo sin cruces, entonces el gráfico se llama planar . Este es el caso, por ejemplo, de su segundo ejemplo. Incluso si el dibujo que tienes muestra un cruce, el segundo dibujo que te di es un dibujo del mismo gráfico pero sin cruce de bordes. Por lo tanto es un grafo plano.
Editar Como se explica en el comentario, los cuatro gráficos iniciales son todos planos, el cuarto se puede dibujar como
bdvg2302
Tomás Lesgourgues
bdvg2302
Tomás Lesgourgues
Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2
Suponiendo que G=(V(G),E(G))G=(V(G),E(G))G=(V(G),E(G)) es un gráfico, ¿qué significa Δ(G)Δ (G)\Delta(G) significa?
¿T1+T2T1+T2T_1+T_2 es plano si T1,T2T1,T2T_1,T_2 son árboles con los mismos vértices?
Problema sobre la existencia de un ciclo de Bruijn.
Pregunta sobre una prueba de "El gráfico GGG no tiene ciclos impares ⟹⟹\implica que GGG es bipartito"
Demostrar que para todo n≥2n≥2n\geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos.
probar que para n≥2n≥2n \geq 2 no existe un grafo simple de n-vértices cuyos vértices tengan grados distintos
¿Alguien puede ayudar a explicar estos diagramas relacionados con gráficos no planos?
¿Por qué encontrar el número cromático es NP-Hard?
Para cada n≥2n≥2n \geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos
Tomás Lesgourgues
bdvg2302
Tomás Lesgourgues