Tipos de grafos<\/strong><\/h2>\n<\/li>\n<\/ul>\n\u00b7Grafo no dirigido asociado:<\/strong> es un grafo dirigido a un grafo con el mismo conjunto de v\u00e9rtices y en el que se han ognorado las direcciones de los v\u00e9rtices.<\/p>\n![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo13-300x56.png\")
<\/a><\/p>\n\u00b7Grafo mixto:<\/strong> contiene tantos arcos como aristas, es decir, contiene ambas cosas.<\/p>\n![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo15.png\")
<\/a><\/p>\n\u00b7Grafo simple:<\/strong><\/p>\n1-No dirigido= sin bucles y no hay dos aristas que unan el mismo par de v\u00e9rtices.<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo16.png\")
<\/a><\/p>\n2-Dirigidos= sin bucles y no hay dos arcos uniendo el mismo par de v\u00e9rtices y con la misma direcci\u00f3n.<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo17.png\")
<\/a><\/p>\nSi un grafo no es simple se llama multigrafo.<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Dibujo-300x297.jpg\")
<\/a><\/p>\nNo es simple ya que tenemos un bucle y dos aristas con la misma direcci\u00f3n uniendo los mismos v\u00e9rtices.<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Dibujo1-300x297.jpg\")
<\/a><\/p>\nEste s\u00ed es simple porque aunque tiene 2 aristas, son de distinta direcci\u00f3n.<\/p>\n
\u00b7Grafo no dirigido completo:<\/strong> si hay al menos una arista (arco) uniendo cada par de v\u00e9rtices distintos.<\/p>\nSi estos grafos son simples se denominan kn<\/sub>.<\/p>\n-kn<\/sub>= grafos completos no dirigidos y simples con \u201cn\u201d v\u00e9rtices.<\/p>\nEjemplo:<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo20.png\")
<\/a><\/p>\n\n- \n
Contar aristas de un grafo<\/strong><\/h2>\n<\/li>\n<\/ul>\nVamos v\u00e9rtice a v\u00e9rtice uniendo con los que todav\u00eda no est\u00e1n unidos. Al final los sumamos.<\/p>\n
Una vez tenemos el n\u00famero de v\u00e9rtices y de aristas\u00a0 se hace lo siguiente: (v\u00e9rtices * aristas)\/2 = aristas del grafo completo<\/p>\n
Para los grafos kn<\/sub> hacemos |A|= (n*(n-1))\/2<\/p>\n\n- \n
Determinar el n\u00famero cr\u00f3matico de un grafo, <\/strong>grafos bipartidos y grafo km,n<\/sub><\/strong><\/h2>\n<\/li>\n<\/ul>\nSe parte el grafo en dos formando un grafo bipartido.<\/p>\n
\u00b7Grafo bipartido:<\/strong> fromado por dos conjuntos de v\u00e9rtices {V1, V2}<\/p>\n-Los v\u00e9rtices de ambos conjuntos han de estar conectados entre s\u00ed pero los de V1 no lo estar\u00e1n entre ellos y tampoco lo estar\u00e1n los de V2.<\/p>\n
-La uni\u00f3n de ambos dar\u00e1 el conjunto completo.<\/p>\n
-Su intersecci\u00f3n dar\u00e1 el conjunto vac\u00edo.<\/p>\n
Ejemplo:<\/p>\n
V1={x, t}<\/p>\n
V2={z, y}<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo21.png\")
<\/a><\/p>\nEn este grafo es sencillo distinguir los dos grupos de v\u00e9rtices pero en un grafo m\u00e1s complejo no es tan sencillo. En estos casos debemos seguir el siguiente procedimiento:<\/p>\n
1-Elegimos un v\u00e9rtice cualquiera.<\/p>\n
2-Ponemos una etiquieta a ese v\u00e9rtice y una distinta para los v\u00e9rtices conectados a \u00e9l, esta etiquieta es distinta al v\u00e9rtice elegido pero com\u00fan para los v\u00e9rtices conectados a \u00e9l.<\/p>\n
Ejemplo:<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo22-300x171.png\")
<\/a><\/p>\nEn este caso hemos empezado etiquetando el v\u00e9rtice \u201c2\u2033 con un 2 y los v\u00e9rtices adyacentes con un \u201c1\u2033, despu\u00e9s el v\u00e9rtice que no es adyacente lo hemos vuelto a etiquetar con un \u201c2\u2033 y sus adyacentes con un \u201c1\u2033.<\/p>\n
Una vez hecho esto tendremos un conjunto formado por los v\u00e9rtices con la etiquieta \u201c1\u2033 y otro formado por la etiquieta \u201c2\u2033.<\/p>\n
V1={0, 1, 3, 4, 6, 7}<\/p>\n
V2={2, 5}<\/p>\n
Ahora se sabe cu\u00e1ntos colores son necesarios para pintar este grafo. Con dos colores ser\u00e1 suficiente ya que la \u00fanica condici\u00f3n para pintarlos es que no hayan dos grafos adyacentes pintados iguales y gracias a esta distinci\u00f3n de conjuntos se puede cumplir dicha condici\u00f3n.<\/p>\n
Para los grafos dirigidos se har\u00e1 con su grafo asociado (para comprobar si es bipartido).<\/p>\n
Tambi\u00e9n se puede tener grafos bipartidos completos<\/strong> si cada v\u00e9rtice de V1 est\u00e1 unido con vada v\u00e9rtice de V2.<\/p>\n![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/bipartido-300x120.jpg\")
<\/a><\/p>\n\u00b7km,n<\/sub><\/strong>: grafo no dirigido bipartido completo y simple con card(V1)=m, card(V2)=n.<\/p>\n<\/a>![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Kmn-300x120.jpg\")
<\/a><\/p>\nSubgrafo y grafo generador<\/strong><\/strong><\/h2>\n\u00b7Subgrafo:<\/strong> si tenemos un grafo G= (V, A) y un grafo H=(V\u2019, A\u2019). H es subgrafo de G si el n\u00famero de v\u00e9rtices y aristas de H es menor o igual al de G.<\/p>\nEjemplo:<\/p>\n
\u00b7Grafo mixto:<\/strong> contiene tantos arcos como aristas, es decir, contiene ambas cosas.<\/p>\n \u00b7Grafo simple:<\/strong><\/p>\n 1-No dirigido= sin bucles y no hay dos aristas que unan el mismo par de v\u00e9rtices.<\/p>\n 2-Dirigidos= sin bucles y no hay dos arcos uniendo el mismo par de v\u00e9rtices y con la misma direcci\u00f3n.<\/p>\n Si un grafo no es simple se llama multigrafo.<\/p>\n No es simple ya que tenemos un bucle y dos aristas con la misma direcci\u00f3n uniendo los mismos v\u00e9rtices.<\/p>\n Este s\u00ed es simple porque aunque tiene 2 aristas, son de distinta direcci\u00f3n.<\/p>\n \u00b7Grafo no dirigido completo:<\/strong> si hay al menos una arista (arco) uniendo cada par de v\u00e9rtices distintos.<\/p>\n Si estos grafos son simples se denominan kn<\/sub>.<\/p>\n -kn<\/sub>= grafos completos no dirigidos y simples con \u201cn\u201d v\u00e9rtices.<\/p>\n Ejemplo:<\/p>\n Vamos v\u00e9rtice a v\u00e9rtice uniendo con los que todav\u00eda no est\u00e1n unidos. Al final los sumamos.<\/p>\n Una vez tenemos el n\u00famero de v\u00e9rtices y de aristas\u00a0 se hace lo siguiente: (v\u00e9rtices * aristas)\/2 = aristas del grafo completo<\/p>\n Para los grafos kn<\/sub> hacemos |A|= (n*(n-1))\/2<\/p>\n Se parte el grafo en dos formando un grafo bipartido.<\/p>\n \u00b7Grafo bipartido:<\/strong> fromado por dos conjuntos de v\u00e9rtices {V1, V2}<\/p>\n -Los v\u00e9rtices de ambos conjuntos han de estar conectados entre s\u00ed pero los de V1 no lo estar\u00e1n entre ellos y tampoco lo estar\u00e1n los de V2.<\/p>\n -La uni\u00f3n de ambos dar\u00e1 el conjunto completo.<\/p>\n -Su intersecci\u00f3n dar\u00e1 el conjunto vac\u00edo.<\/p>\n Ejemplo:<\/p>\n V1={x, t}<\/p>\n V2={z, y}<\/p>\n En este grafo es sencillo distinguir los dos grupos de v\u00e9rtices pero en un grafo m\u00e1s complejo no es tan sencillo. En estos casos debemos seguir el siguiente procedimiento:<\/p>\n 1-Elegimos un v\u00e9rtice cualquiera.<\/p>\n 2-Ponemos una etiquieta a ese v\u00e9rtice y una distinta para los v\u00e9rtices conectados a \u00e9l, esta etiquieta es distinta al v\u00e9rtice elegido pero com\u00fan para los v\u00e9rtices conectados a \u00e9l.<\/p>\n Ejemplo:<\/p>\n En este caso hemos empezado etiquetando el v\u00e9rtice \u201c2\u2033 con un 2 y los v\u00e9rtices adyacentes con un \u201c1\u2033, despu\u00e9s el v\u00e9rtice que no es adyacente lo hemos vuelto a etiquetar con un \u201c2\u2033 y sus adyacentes con un \u201c1\u2033.<\/p>\n Una vez hecho esto tendremos un conjunto formado por los v\u00e9rtices con la etiquieta \u201c1\u2033 y otro formado por la etiquieta \u201c2\u2033.<\/p>\n V1={0, 1, 3, 4, 6, 7}<\/p>\n V2={2, 5}<\/p>\n Ahora se sabe cu\u00e1ntos colores son necesarios para pintar este grafo. Con dos colores ser\u00e1 suficiente ya que la \u00fanica condici\u00f3n para pintarlos es que no hayan dos grafos adyacentes pintados iguales y gracias a esta distinci\u00f3n de conjuntos se puede cumplir dicha condici\u00f3n.<\/p>\n Para los grafos dirigidos se har\u00e1 con su grafo asociado (para comprobar si es bipartido).<\/p>\n Tambi\u00e9n se puede tener grafos bipartidos completos<\/strong> si cada v\u00e9rtice de V1 est\u00e1 unido con vada v\u00e9rtice de V2.<\/p>\n \u00b7km,n<\/sub><\/strong>: grafo no dirigido bipartido completo y simple con card(V1)=m, card(V2)=n.<\/p>\n <\/a> \u00b7Subgrafo:<\/strong> si tenemos un grafo G= (V, A) y un grafo H=(V\u2019, A\u2019). H es subgrafo de G si el n\u00famero de v\u00e9rtices y aristas de H es menor o igual al de G.<\/p>\n Ejemplo:<\/p>\n![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/11\/Sin-t\u00edtulo13.png\")
<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n\n
Contar aristas de un grafo<\/strong><\/h2>\n<\/li>\n<\/ul>\n
\n
Determinar el n\u00famero cr\u00f3matico de un grafo, <\/strong>grafos bipartidos y grafo km,n<\/sub><\/strong><\/h2>\n<\/li>\n<\/ul>\n
<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\nSubgrafo y grafo generador<\/strong><\/strong><\/h2>\n
![<\/a>](\"..\/..\/romulo\/files\/2010\/11\/Sin-t%C3%ADtulo24.png\"){kind=link}