Graphs Flashcards
What is an Undirected Graph?
A pair G = (V, E)
Where V is a set of vertices and E is a set of edges
What is the degree of a vertex?
The number of edges connected to a vertex
What is an adjacency list?
A linked list which stores information about which vertex is adjacent to which other vertex
What is an adjacency matrix?
An n × n matrix (Table) where the element
at row i and column j is a 1 if there is an edge between vertex i and vertex j, otherwise it is 0.
(Good for dense graphs with more edges than vertexes)
What is are directed graphs?
If a pair of vertices (u, v) is not the same as the pair (v, u), the graph is called a directed graph.
Uses arrows instead of lines.
What is a path?
A sequence of edges connecting one vertex to another
What can be said about a path where every vertex is distinct?
It is a simple path
What is a cycle?
A path that starts and ends at the same vertex
What is a connected graph?
A graph where every vertex is connected by at least one edge
(Not a complete graph)
What is a Euler cycle?
A cycle that visits every edge only once.
What makes a graph planar?
If it can be drawn on a plane without any crossing edges.
What is a clique?
A set of vertexes within a graph that are all connected by an edge.
What is a tree?
A connected, acyclic graph.
What do these terms mean when talking about trees:
- Root
- Leaf
- Parent
A root is the topmost vertex
A leaf is a vertex without any children (Vertex of 0)
A parent is a vertex with vertexes directly below it
What is a binary tree?
A tree with a degree of 2
