Week 6: Graphs Flashcards
1
Q
What is a graph?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/120/993/a_image_thumb.png?1659047588)
2
Q
What are the following:
Directed edge
Undirected edge
Directed graph or digraph
Undirected graph
Mixed graph
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/018/a_image_thumb.png?1659047641)
3
Q
What are the following:
End vertices (or endpoints) of an edge
Edges incident on a vertex
Adjacent vertices
Degree of a vertex
PArallel edges
Self-loop
Simple graph
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/050/a_image_thumb.png?1659047759)
4
Q
What are the following:
path
simple path
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/112/a_image_thumb.png?1659047789)
5
Q
What are the following:
Cycle
Simple cycle
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/121/a_image_thumb.png?1659047808)
6
Q
What are the properties of a graph?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/134/a_image_thumb.png?1659047827)
7
Q
What is a complete graph/clique?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/141/a_image_thumb.png?1659047846)
8
Q
What is a connected graph?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/152/a_image_thumb.png?1659047864)
9
Q
What is a tree?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/159/a_image_thumb.png?1659047877)
10
Q
What is a forest?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/164/a_image_thumb.png?1659047891)
11
Q
What is a subgraph?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/172/a_image_thumb.png?1659047902)
12
Q
What is a connected component?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/174/a_image_thumb.png?1659047917)
13
Q
Example of connected components:
A
Answer: 3
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/177/a_image_thumb.png?1659047954)
14
Q
What is the Edge List DS for storing a graph?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/190/a_image_thumb.png?1659047979)
15
Q
What is the Adjacency List DS for storing a graph?
A
![](https://s3.amazonaws.com/brainscape-prod/system/cm/391/121/198/a_image_thumb.png?1659047998)