Projeto e Análise de Algoritmos - Aula 11 - Conceitos básicos e representação de grafos

[Música] ah [Música] hola personal sean bienvenidos 'nos aula número 11 de proyectos y análisis de algoritmos esa aula va a ser sobre grafos vamos a presentar algunos conceptos básicos sobre él y cómo representar grafos un grafo en más tracción que permite codificar relacionamiento entre pares de objetos es el idioma definición informado aunque que son esos objetos son los vértices del grafo los relacionamientos son las aristas de graf veamos algunos ejemplos suponga que tenemos un conjunto de votos comerciales entre diferentes edades que están mostradas en ese mapa aquí en todos los vuelos comerciales posibles cuáles son

los objetos ahí objetos son así de asís y cuál es su relacionamientos un relacionamiento de hubo comercial entre dudas existente entre dos ciudades en otro ejemplo suponga que tenemos un conjunto de páginas web y agente un link de una página web y para otra más un link para otra lento aunque que serían los objetos aquí son los objetos son las páginas web y los saneamientos son los links de una página para otro existe un tipo de dados abstractos que llamado detalle o quartet un conjunto de operaciones asociadas en la estructura de dados que puede ser

usado para modelar tales situaciones cual que ese tipo de abstracto de dados el graf muchos problemas en computación pueden ser resolví dos con un mismo algoritmo en encima de la misma extracción que un grafo por ejemplo supone que deseamos saber cuántos caminos existen para ir a citas y si esa tenacidad si lo aquí tenemos un mapa con las entradas entre una ciudad y otra o queremos saber cuál que un menor camino entre ácidas ficticias ácidas y ypsilon o queremos saber si existe un camino para idiomas y dady existe otra ciudad ipsi lo será todo eso

puede ser visto aquí y eso puede ser presentado como un grafo aunque cause los vértices en ese grafos vértice son ser ácidas es lo que vamos a abrazar esto somos eras estradas entre esas ciudades un otro ejemplo queremos saber si dudas personas están conectadas a través de una secuencia de relacionamientos relacionamientos declarados por ejemplo de amistad como un menor camino queremos saber con qué un mediador camino entre dos personas podemos representar y su como grafos y resolver un problema con un problema en grafos ok que va un ser los vértices sus vértices vamos heras peso

así que vamos a lanzar estas un relacionamiento declarados entre las personas por ejemplo relacionamiento de amistad así como ésta feli en todo por qué definición del grafo un grafo un conjunto de vértices aristas y vértice de un objeto simples que puede tener un nombre y otros atributos adicionales y hacer estas son la conexión entre estos creativos aquí tenemos un ejemplo tenemos seis vértices y 1 2 3 4 5 6 7 a éstas formalmente un grafo y he definido por una dupla de a en que ve el conjunto de vértices y ya el conjunto de aristas

ok tenemos dos tipos de grafo un grafo direccionado geógrafo no direccionado pensamos primero un grafo direccionado un grafo direccionado y en un par de a en que ve el conjunto finito de vértices afanamos y dada una relación binaria en b esto existe esa relación binaria que sería ares que representaré esta va a ser representado como un par ordenado de vértices no aquí vamos tener por ejemplo aquí haré esta va a ser un paro ordenado comencé en b y terminen d esta vez por ejemplo esto de aquí las hay de vértice ve y entran un vértice

y así dice moscú vértice adyacente se decía ya sentí un vértice b paul y de existir aristas de un vértice para el mismo por ejemplo aquí tenemos mar está que va a idear la idea y lleguen a esa es llamada de aire está del tipo se of blood y ahora vayamos a definición de graf o no direccionado un grafo no direccionado también un par de ad en que en que el conjunto de aristas que no son ordenadas y hacer estas v idea son consideradas como una única ar está todo aquí por ejemplo tenemos su madre

está entre 4 y 3 no existe una orden argentino falta de cuatro para tres de tres para cuatro y se considera en la comuna única tanto el sistema orden entre sus vértices existe la relación de adyacencia que es simétrica y por ejemplo aquí 4 y 6-3 y 3-6 4 a ustedes luz no son permitidos en ese caso para grafos no direccionados te aconsejamos una característica dos grafos la verdad es una característica dos vértices que sería un grado graus de un vértice en grafos comencemos por direccionados podemos tener diferentes grados un grado de salida un grado

de entrada y grave en grado de un vértice un grado de salida en un número de áreas que están en su vértice o grado de entrada y un número de áreas que llegan no vértice y el grado de un vértice asoma de xestores graus anteriores lo dejamos aquí un ejemplo considerando un vértice de élite en grau de salida 3 porque te entregaré estás hindú de l y tengo grado de entrada aún porque tengo madre está entrando en el y grau de él y de ese betis en general 4 que sería suma de estos valores el

grado de un vértice en grafos no direccionados es simplemente un número de áreas que inciden en el por ejemplo vamos ver aquí de aquí a poco vamos porque tenemos aquí otro que 16 y el inau ten niño me conexión con nosotros vértices este de aquí sería un vértice de grado 0 y también llamado de vértice solado o no conectado el y no te mínima haré esta que siguen el ahora vayamos aquí con otro vértice un vértice 51 grau de vértice 53 existen tres aristas que inciden en él ok vayamos ahora como representa grafos coke a

manera de representar grafos ya sabemos que un grafo de un par de a en que desde el conjunto de vértices y al conjunto de estas parece simple no aquí ve sería 1 2 3 4 5 y 6 está aquí ya sabe estas 11 bastante está entre unidos steny madre está entre 1 y 5 de animales entre 2 y 3 se merece entre 2 y 5 entre 3 y 4 entre 4 y 5 entre 4 y 6 tenemos ahí en todo un conjunto de áreas maestra pregunta en un computador como que pudo representar ese grafo existen

dudas formas podemos representar el como una matriz de adyacencia o como una colección de listas de adyacencias porque la representación más eficiente o más adecuado a eso va a depender la va a depender las características su gráfica y dependiendo que las personas precisa hoy vamos a ver de aquí a poquito cuando usan cada una de las con comencemos con matriz de adyacencia porque tenemos una matriz la matriz asociamos birdies esas líneas y columnas a matriz o elemento de matriz va a indicar si existe una de ésta o no en la matriz de adyacencia va a

ser una matriz de nfs cn con un número de vértices en que una posición y yo está de esa matriz vamos a hacer un examen si si existe un arco omar está tu vértice y para un 26 j y va a ser cero caso contrario y parágrafos ponderados que un grafo ponderado de un grafo que tenga un valor de ésta que fue colocar un ejemplo de grafo pondera entonces ponía que tenemos ese gráfico que representa que representa a ciudades entonces la ciudad ya la ciudad y así dice yo sé que a distancia entre la ciudad

y hay de 10 kilómetros entre la ciudad y page es en kilómetros y entre hace ya 200 este de aquí sería un grafo ponderado porque porque no tengo basa de estas masas al enlazar ese sureño un peso asociado de ellis en el is que en este caso sería a distancia entre ellos para representar este grafo con una matriz de adyacencia reposo colocar una posición idiota de esa matriz a un peso asociado con aire estado vértice para el vértice jot si no existir madre está de y para ello está esto por ejemplo vamos porque aquí tengo

un vértice otro vértice d y yo tenía una conexión aquí más no tengo conexión con una que tuvo colocar que el valor fue colocado después utiliza un valor que no pueda ser usado como rótulo o peso un valor por ejemplo menos infinito en ese caso un valor negativo ok fijamos aquí un ejemplo de matriz de adyacencia para ese grafo direccionado en este caso que vamos trenton tenemos 2 366 y vértices vamos a hacer una matriz de secheep orsay y en cada posición sin existir un arco podemos colocar un punto por ejemplo entre a y b

existe un arco colocamos aquí entre bs existe un arco entonces colocar un aquí entre beige entre b y d existe un arco y entre veía también aquí aquí para hacer un mismo tengo un arco para que vaya para él y así porque son fighter um si existe realmente un arco entre uberti 6 y 26 jot para un grafo no direccionado va a ser un mismo no tengo madre está entre 6 y 4 entre una posición 640 en la posición 46 también voltear un alambre en que aquí a como si existiese un mar está de ida

y mar está de vuelta a todos y yo llamo en esa matriz más lo vamos a hacer para todos los elementos a matriz si hallamos para esa matriz es la de una matriz simétrica cuando usar cuando no usar vamos ver cuándo usar y cuando no usar considere que tenemos un grafo con muchos vértices y relativamente pocas aristas no sé si tenemos un grafo grande y espacio aunque que vaya a acontecer esa matriz bayter pocos números y muchos números ceros en una matriz estará formada principalmente de ceros y eso va a consumir mucha memoria wawel es

necesario toda la gente podría pensar en una u otra manera de representar esos casos cuando tenemos relativamente pocas aristas cuando grafo espacio a matrices de esencia debe ser utilizada para grafos de eso su contrario de espacio en que a cantidad idea de éstas el próximo la cantidad de vértices elevado cuadrado se le hace un grafo completo un tiempo necesario para cesar un elemento de independencia debe idea esa es una característica importante de las matrices de ausencia en o de un no se puede accesar el valor de una posición de matriz en todo para saber si

existe un mar está entre liotta y su efecto en odio la matriz de adyacencia muy útil pero a boris mohsén que necesitamos saber con rapidez si existe o madre está ligada mirando los datos como ya fue liceo de un cualquiera desventaja en la matriz de adyacencia la matriz necesita omega de tamaño la cantidad y de bertiz elevado al cuadrado de espacio y hay tobago ahora ya sabemos cómo representa grafos densos con matriz de asia ciencia necesitemos grafos espacios y son gran existen muchas veces como que representamos ese graph contemos ahora una otra opción que sería

colección de listas de adyacencia o que facemos ahora vamos a asociar a cada vértice una lista de vértices adyacentes que vamos a usar entonces vamos a usar vamos a crear un vector h abelló está acá db listas una para cada vértice b y para cada para cada vértice que pertenece a la lista de vértices la lista de adyacencias a de jt va a consistir de todos sus vértices hacia sanchis aún estoy en esa lista vamos a usted todos sus vértices de taiz que existe una resta de eeuu para b entonces llamamos a coro es simple

tenemos a quinto un oso grafo dirigido entonces podemos crear una colección de listas de adyacencia ok tenemos cuantos cuantos verdes estemos aquí tenemos entonces ser una colección de sets y listas y adyacencia una para cada vez dice ok tenemos una para cada vértice lo que vamos a hacer en cada en cada una de esas posiciones tema lista de ellas ciencia que serían sus sus vértices que son adyacentes no por ejemplo aquí de alias antza en toda una lista de a va a estar b después y d i son adyacentes sabe en toda una lista debe

como estar c d y e y un mismo para los demás elementos para los demás vértices efe por ejemplo no te ninguén no tengo ni un vértice adyacente a él y está vacío entonces símbolo está representando fácil o no y aquí la colección de listas de agencias para un grafo no dirigido como que va a ser idéntico por ejemplo pero el vértice un vértice en dos vértice that jazz' en israel y un 52 están aquí ok los cinco vértices arias en esa élite tengo cuatro tengo dos y también tengo un punto aquí 15 tienen 42

100 precisamente eso de aquí qué hunter las listas ante cosas repetidas porque aquí hay gente en tanto ahora está la cuenta de fontanet esta analista 25 y 15 están alistados ok es verdad existe una lista de adyacencia son y llegado almacenados en una orden arbitraria fecha faltan dos o no es la de la anterior normalmente si vos es observar aquí esa lista está en una orden arbitraria si alguien si quisiera saber por ejemplo si cinco días en sudores hay en chivay tener que verificar todos sus elementos de esa lista de aquí esa es una desventaja

que asuma los complementos de todas las listas de adyacencias en un caso de ser un grafo orientado a su tamaño la cantidad y está la verdadera cantidad de aristas del grafo exige un grafo no orientado a ser dos veces la cantidad ideal está su gráfico así el espacio requerido por esa representación va a ser o debe más a la sagrada orientado con oriental porque como usted una colección de tamaño ve y agency bayter listas cuya suma total va a ser máximo dos veces a para casos de grafeno orientado y por eso que aquí en masa

se podría hacer aquí dos veces esa mensualidad la misma donde hemos no final o de tu tamaño debe más su tamaño de a en esta representación más adecuada para grafos espacios cuando hay mucho menor duque la cantidad ayudaré está hace mucho menor que la cantidad y de vértices elevado al cuadrado y compacta y he usado en la mayoría de las aplicaciones por en el apoyo y consumir o debe para determinar si existe un madre está entre un 26 y 26 de lehman que esa lista de adyacencias no está ordenada que acontece si en alguna de

las listas ciencias en seúl tengo muchos elementos que vaya a acontecer water que procurar en todos esos elementos es por eso que puede consumir o debe para determinar si existe un área de centro vértice y vértice j lo que hice fue nos aula número 11 sobre los conceptos básicos de grafos y representación de grafos espero que nos enseñan costados [Música] 2 [Música] [Música] [Música] más