Projeto e Análise de Algoritmos - Aula 11 - Conceitos básicos e representação de grafos
Summary
TLDRThis 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
📚 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.
🔍 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.
📊 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.
🗂️ 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.
🔚 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.
Mindmap
Keywords
💡Graphs
💡Vertices
💡Edges
💡Directed Graph
💡Undirected Graph
💡Adjacency
💡Degree of a Vertex
💡Graph Representation
💡Adjacency Matrix
💡Adjacency List
💡Weighted Graph
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
Browse More Related Video
AQA A’Level Graphs
Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 1.3 - Choice of Graph Representation
#1 Struktur Data Tree (Pohon) & Graph (Graf) - Berpikir Komputasional Kelas 9 | Informatika Fase D
6.10 Topological Sorting (with Examples) | How to find all Topological Orderings of a Graph
Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 1.1 - Why Graphs
Motion Class 9 One Shot in 10 mins | Best CBSE Class 9 Physics Revision Strategy | Abhishek Sir
5.0 / 5 (0 votes)