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

Summary

This video script covers fundamental concepts of graphs in computer science, explaining how graphs can model relationships between objects. It introduces vertices and edges, differentiating between directed and undirected graphs, and discusses graph representations, including adjacency matrices and lists. The script also touches on weighted graphs and the importance of choosing the right representation based on the graph's characteristics, such as density and sparsity.

Takeaways

• 😀 Graphs are a fundamental data structure used to model pairwise relationships between objects, known as vertices, and the connections between them, known as edges.
• 🌐 Examples of graph applications include modeling commercial flights between cities, web pages and hyperlinks, and social networks through friendship links.
• 📚 A graph is formally defined by a pair (V, E) where V is a set of vertices and E is a set of edges that connect these vertices.
• 🔄 There are two types of graphs: directed graphs, where edges have a direction, and undirected graphs, where edges do not.
• 🔗 In directed graphs, edges are represented as ordered pairs of vertices, indicating the direction of the relationship, while in undirected graphs, edges are unordered pairs.
• 🔢 Graphs can be weighted, where each edge has an associated value or weight, such as the distance between cities in a map.
• 📊 Two common ways to represent graphs are through adjacency matrices, which use a grid of values to indicate the presence of edges, and adjacency lists, which use a collection of lists to store the adjacent vertices for each vertex.
• 💾 Adjacency matrices are space-consuming and best suited for dense graphs with many edges, while adjacency lists are more memory-efficient and suitable for sparse graphs with fewer edges.
• 🔄 The degree of a vertex, which is the number of edges incident to it, can be different in directed and undirected graphs. In directed graphs, it's further divided into in-degree and out-degree.
• 🔍 Algorithms for graph traversal, such as finding paths between vertices, can be implemented using either adjacency matrices or lists, depending on the graph's characteristics and the specific requirements of the problem.

Q & A

What is the main topic of the lecture?

The main topic of the lecture is graphs, including basic concepts, representation, and how they can be used to encode relationships between pairs of objects.

What are the two main components of a graph?

The two main components of a graph are vertices, which represent the objects, and edges, which represent the relationships between these objects.

Can you provide an example of how graphs can be used to represent real-world scenarios?

Yes, one example is using graphs to represent commercial flights between different cities, where the cities are vertices and the flights are edges.

What is a directed graph?

A directed graph is a graph where the edges have a direction, meaning the relationship between vertices is not necessarily symmetrical.

What is an undirected graph?

An undirected graph is a graph where the edges do not have a direction, implying that the relationship between vertices is symmetrical.

What is the difference between a weighted and an unweighted graph?

In a weighted graph, each edge has an associated value or weight, whereas in an unweighted graph, edges do not have any associated values.

What are the two methods mentioned for representing graphs in a computer?

The two methods mentioned for representing graphs in a computer are using an adjacency matrix and using a collection of adjacency lists.

When would you use an adjacency matrix to represent a graph?

An adjacency matrix is typically used when the graph is dense, meaning it has a large number of edges relative to the number of vertices.

When would you use a collection of adjacency lists to represent a graph?

A collection of adjacency lists is typically used when the graph is sparse, meaning it has relatively few edges compared to the number of vertices.

What is the main disadvantage of using an adjacency matrix for a sparse graph?

The main disadvantage of using an adjacency matrix for a sparse graph is that it requires a lot of memory due to the large number of zero entries, as most of the potential edges are absent.

What is the main advantage of using a collection of adjacency lists for a graph?

The main advantage of using a collection of adjacency lists is that it is space-efficient for sparse graphs, as it only stores the edges that actually exist.

Outlines

00:00

📚 Introduction to Graphs and Basic Concepts

The video script introduces the concept of graphs, a fundamental data structure used to represent relationships between objects, such as commercial flights between cities or links between web pages. It explains the definition of a graph, which consists of vertices (objects) and edges (relationships). The script also touches on the applications of graphs in solving various computational problems, like finding the shortest path between two points or determining connectivity between entities. The importance of understanding graphs is highlighted, as they can be used to model a wide range of scenarios.

05:09

🔍 Graph Representations and Types

This paragraph delves into the different types of graphs, specifically directed and undirected graphs, and how they are represented. Directed graphs use ordered pairs to represent relationships, while undirected graphs consider the relationships to be symmetrical, without order. The script also discusses the concept of graph vertices and edges, and how they are formally defined. It further explains the difference between adjacency in directed and undirected graphs and introduces the notion of graph degree, which measures the number of edges connected to a vertex.

10:10

📊 Graph Representation Techniques: Adjacency Matrix

The script explains two primary methods for representing graphs in a computer: the adjacency matrix and the adjacency list. The adjacency matrix is a grid where rows and columns represent vertices, and the cells indicate the presence of an edge between two vertices. This method is suitable for dense graphs and includes a discussion on weighted graphs, where edges have a numerical value representing a cost or distance. The script also provides an example of how to represent a directed graph using an adjacency matrix, emphasizing the need to fill the matrix symmetrically for undirected graphs.

15:11

🗂️ Exploring Adjacency Lists for Graph Representation

The script presents the second method of graph representation, the adjacency list, which associates each vertex with a list of adjacent vertices. This method is more space-efficient for sparse graphs, where the number of edges is much less than the square of the number of vertices. The paragraph discusses the advantages of using adjacency lists, such as ease of implementation and reduced memory usage, and also mentions the potential downside of having to search through lists to find connections between vertices.

20:13

🔚 Conclusion on Graph Representations and Applications

In conclusion, the script summarizes the importance of understanding different graph representations and their applications. It emphasizes the need to choose the right representation based on the characteristics of the graph and the specific requirements of the problem being solved. The video ends with a recap of the key points covered in the lesson, reinforcing the concepts of graph theory and their relevance in computer science.

Keywords

💡Graphs

Graphs are a fundamental concept in the video, representing a structure that encodes relationships between pairs of objects, known as vertices. They are essential in computer science for modeling various situations, such as social networks, transportation systems, and the internet. The script uses graphs to illustrate complex relationships in a visual and structured way, for instance, when discussing commercial flights between cities or web pages linked by hyperlinks.

💡Vertices

Vertices in the context of the video are the objects or entities within a graph. They represent the fundamental units that are connected by edges or arcs. The script mentions vertices when explaining the structure of a graph, such as cities in a flight network or web pages in a hyperlink structure.

💡Edges

Edges, also referred to as arcs in the script, are the connections or relationships between vertices in a graph. They are crucial for defining the structure of the graph and the nature of the relationships between the objects being modeled. The video uses edges to demonstrate how commercial flights connect cities or how web pages are interconnected through hyperlinks.

💡Directed Graph

A directed graph, as explained in the script, is a type of graph where the edges have a direction, indicating a one-way relationship between vertices. This is contrasted with an undirected graph, where the relationships are bidirectional. The concept is used to illustrate scenarios where the direction of the relationship is significant, such as one-way streets in a road network.

💡Undirected Graph

An undirected graph is introduced in the script as a graph where the edges do not have a direction, meaning the relationships between vertices are bidirectional. This type of graph is used to represent scenarios where the connection between objects is mutual, such as friendships in a social network.

💡Adjacency

Adjacency in the video refers to the concept of vertices being directly connected by an edge in a graph. The script discusses adjacency to explain how graphs can represent close relationships or direct connections between objects, such as the immediate connections between cities in a transportation map or web pages.

💡Degree of a Vertex

The degree of a vertex, as mentioned in the script, is a measure of the number of edges incident to a vertex. It can be further divided into the in-degree (for directed graphs), which counts the number of incoming edges, and the out-degree, which counts the outgoing edges. In undirected graphs, the degree simply refers to the total number of edges connected to the vertex. The script uses the degree to explain the connectivity of vertices within a graph.

💡Graph Representation

Graph representation is a key topic in the script, discussing how graphs can be represented in a computer system. Two primary methods are introduced: adjacency matrix and adjacency list. The script explains the use of these representations depending on the characteristics of the graph, such as whether it is dense or sparse, and the specific requirements of the problem being solved.

💡Adjacency Matrix

An adjacency matrix is a representation method for graphs discussed in the script. It involves a square matrix where the rows and columns represent vertices, and the entries indicate the presence or absence of an edge between vertices. The script uses the adjacency matrix to illustrate how to represent relationships in a graph, especially in dense graphs where many vertices are connected.

💡Adjacency List

An adjacency list, as described in the script, is another method for representing graphs. It involves associating each vertex with a list of adjacent vertices. This representation is particularly useful for sparse graphs where there are relatively few connections between a large number of vertices. The script explains how adjacency lists can efficiently represent graphs with minimal connections.

💡Weighted Graph

A weighted graph is introduced in the script as a type of graph where edges have an associated weight or cost. This could represent distances, costs, or other measurable attributes of the relationships between vertices. The script uses the concept of a weighted graph to illustrate how additional information can be incorporated into graph structures, such as the distances between cities in a transportation network.

Highlights

Introduction to basic concepts of graphs and their representation.

Graphs as a language for encoding relationships between pairs of objects.

Examples of graphs include commercial flights between cities and web pages with links.

Graphs can model various computational problems like finding paths between cities or the shortest path.

Definition of a graph as a set of vertices and edges.

Explanation of directed and undirected graphs.

Differentiation between vertices and edges in graph representation.

Concept of graph degree, including in-degree, out-degree, and total degree.

Use of adjacency matrices to represent graphs.

Adjacency matrices for weighted graphs, where weights can represent distances or costs.

Comparison between using adjacency matrices for dense and sparse graphs.

Introduction of adjacency lists as an alternative to matrices for graph representation.

Advantages of adjacency lists for sparse graphs and their space efficiency.

How to represent directed and undirected graphs using adjacency lists.

Discussion on when to use adjacency matrices and when to use adjacency lists based on graph characteristics.

The impact of graph representation on the efficiency of algorithms for graph traversal and pathfinding.

Conclusion summarizing the importance of understanding graph representation for problem-solving in computer science.

Transcripts

[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