Ejercicio · ZW-GRADO-DE-UN-VERTICE-005 · ★★☆ Intermedio
¿Cuál de estas listas puede ser la lista de grados de un grafo simple?
Elige una opción.
Ver respuesta
- B. 3, 3, 2, 2
Explicación
Se obtiene quitando una arista a un grafo completo de 4 vértices. 3,3,3,1 es imposible (tres vértices de grado 3 tocan al cuarto); 3,2,2 suma impar; en 4,2,2,1 un vértice de grado 4 necesitaría 5 vértices.
Repasa el concepto: Grado de un vértice
El grado \(\deg(v)\) de un vértice \(v\) es el número de aristas del grafo (el conjunto \(E\)) que lo tienen como extremo.
\[\deg(v)=\bigl|\{e\in E:\ v\in e\}\bigr|\]
Más ejercicios de grado de un vértice
- ZW-GRADO-DE-UN-VERTICE-001 Un grafo tiene vértices 1,2,3,4 y aristas \1,2\,\1,3\,\1,4\,\2,3\. ¿Cuál es deg(1)?
- ZW-GRADO-DE-UN-VERTICE-002 Un grafo tiene aristas ab, ac, ad, bc, de. ¿Cuál es el grado del vértice c?
- ZW-GRADO-DE-UN-VERTICE-003 Un grafo tiene 7 aristas. ¿Cuánto vale la suma de los grados de todos sus vértices?
- ZW-GRADO-DE-UN-VERTICE-004 Un grafo tiene cinco vértices con grados 3, 3, 2, 2 y 2. ¿Cuántas aristas tiene?
- ZW-GRADO-DE-UN-VERTICE-006 ¿Cuál es el grado de cada vértice del grafo completo K_6?
- ZW-GRADO-DE-UN-VERTICE-007 Un grafo tiene 7 vértices. ¿Cuál de estos números NO puede ser la cantidad de vértices de grado imp…
- ZW-GRADO-DE-UN-VERTICE-008 Un grafo tiene 12 aristas y todos sus vértices tienen grado 3. ¿Cuántos vértices tiene?
- ZW-GRADO-DE-UN-VERTICE-009 Un grafo simple tiene 6 vértices y uno de ellos es aislado. ¿Cuál es el mayor grado que puede tener…