GRAFOS ESPECIALES (Matemática discreta)

Summary

El guion habla sobre diferentes tipos de grafos simples y especializados. Se describen el grafo nulo sin aristas, el grafo completo donde todos los vértices están conectados, los ciclos con vértices unidos en un círculo y las ruedas, que son ciclos con un vértice central. También se mencionan los grafos de电器, que representan cadenas de bits, y los bipartitos, donde los vértices se pueden dividir en dos grupos sin conexiones entre los mismos. Finalmente, se explican los subgrafos, que pueden ser abarcadores o inducidos, dependiendo de si incluyen todos los vértices o faltan algunos.

Takeaways

• 😀 Un grafo nulo es un conjunto de vértices sin aristas.
• 🌐 Los grafos completos, denotados como K_n, tienen cada vértice conectado con cada uno de los demás.
• 🔁 Los ciclos, denotados como C_n, son grafos donde hay un camino cerrado por cada par de vértices.
• 🚲 Las ruedas, denotadas como W_n, son grafos que se obtienen añadiendo un vértice central a un ciclo y conectándolo con todos los vértices del ciclo.
• 💾 Los grafos de Hamming, denotados como Q_n, representan cadenas de bits y se construyen copiando y conectando subgrafos anteriores.
• 🔑 Los grafos bipartitos se pueden dividir en dos conjuntos de vértices tales que no hay aristas entre vértices del mismo conjunto.
• 🔄 Los grafos bipartitos completos, denotados como K_{m,n}, son aquellos en los que cada vértice de un conjunto está conectado con todos los vértices del otro conjunto.
• 📚 Los subgrafos pueden ser abarcadores, incluyendo todos los vértices del grafo original, o inducidos, que pueden tener menos vértices que el original.
• 🔗 Los subgrafos inducidos son formados por un conjunto específico de vértices y todas las aristas que los conectan.
• 📐 Los subgrafos abarcadores mantienen la cantidad de vértices del grafo original, pero pueden tener menos aristas.

Q & A

¿Qué es un grafo nulo?

Un grafo nulo es un grafo que consta solamente de vértices sin ninguna arista. Por ejemplo, un grafo nulo con n=1 tiene un vértice, con n=2 tiene dos vértices y con n=3 tiene tres vértices.

¿Cómo se denota un grafo completo y qué características tiene?

Un grafo completo se denota con la letra K y un subíndice n, donde n indica la cantidad de vértices. Estos grafos tienen la particularidad de que todos los vértices están unidos por al menos una arista.

¿Cuál es la diferencia entre un grafo simple y un grafo completo?

Un grafo simple puede tener vértices y aristas sin restricciones específicas, mientras que un grafo completo tiene todas las posibles aristas entre los vértices.

¿Qué es un ciclo en un grafo y cómo se denota?

Un ciclo en un grafo es una secuencia de vértices donde cada vértice está conectado por una arista al siguiente, y el último vértice está conectado por una arista al primero. Estos se denotan con la letra C y un subíndice n, donde n es el número de vértices.

¿Qué es una rueda en un grafo y cómo se obtiene?

Una rueda en un grafo se obtiene a partir de un ciclo, al añadir un vértice al centro y unirlo con los vértices del ciclo. Se denota con la letra W y un subíndice n, donde n indica la cantidad de vértices en la rueda.

¿Qué representan los vértices en los grafos de electivos?

En los grafos de electivos, los vértices representan cadenas de bits de longitud 1. Por ejemplo, en el grafo de longitud 1, los vértices son cadenas de bits de una longitud de 1.

¿Cómo se construye un grafo de electivos de longitud 2 (Q2)?

Para construir un grafo de electivos de longitud 2 (Q2), se copian dos veces el grafo de longitud 1 y se conectan por medio de una arista si los vértices difieren en al menos un bit.

¿Qué es un grafo bipartito y cómo se identifica?

Un grafo bipartito es un grafo cuyo conjunto de vértices se puede dividir en dos subconjuntos distintos, de tal manera que cada arista conecta un vértice de un subconjunto con un vértice del otro subconjunto. Se identifica al poder colorear los vértices de cada subconjunto con diferentes colores sin que haya dos vértices adyacentes del mismo color.

¿Qué se entiende por grafo bipartito completo y cómo se denota?

Un grafo bipartito completo es un grafo bipartito donde hay una arista entre cada vértice de un subconjunto y cada vértice del otro subconjunto. Se denota con la letra K y dos subíndices m y n, donde m y n son la cantidad de vértices en cada subconjunto.

¿Qué es un subgrafo y cómo se obtiene?

Un subgrafo es una parte de un grafo original que se obtiene al eliminar algunos vértices y sus aristas incidentes. Puede ser un subgrafo abarcador, que incluye todos los vértices del grafo original, o un subgrafo inducido, que incluye algunos vértices y todas las aristas entre ellos.