Subgráficos inducidas

Question

¿Estoy un poco confundido sobre la parte de "inducido" significa esto que el conjunto de vértices y el conjunto de bordes que se dan, que cada vértice está conectado a cada otro vértice? O por ejemplo, qué pasa si tengo un conjunto de vértices y un conjunto de aristas, pero uno de los vértices no está conectado a cualquier otro vértice. ¿Esto se consideraría un gráfico? ¿o incluso más específico un grafo inducido? Gracias

¿Además, estos subgráficos pueden contener ciclos?

Answer 1

Un subgrafo de $G$ es cualquier subconjunto de a $V(G)$ y cualquier subconjunto de a $E(G)$ que es en sí mismo un gráfico. Por ejemplo, el ciclo de seis vértices es un subgrafo de la completa bipartito gráfico en ocho vértices (elija tres vértices de cada una partita y el conjunto adecuado de los bordes para formar un ciclo).

Un subgrafo inducido es cualquier subconjunto $S$ $V(G)$ con el conjunto de borde $$ \{uv \mediados de la u,v \S \text{ y } uv \in E(G)\}. $$ En palabras, elija sólo el vértice establecido para su subgrafo inducido y, a continuación, un borde de conectar dos de los vértices en el subgrafo inducido si y sólo si se presentan en el gráfico original. Por ejemplo, si elegimos el mismo seis vértices como en el ejemplo anterior, la inducida por el subgrafo debe ser el total gráfico bipartito en seis vértices. No tenemos la libertad de dejar fuera de los bordes, como hicimos con subdiagramas. Debemos tomar todos y sólo los bordes entre los vértices especificados.