Graphs Flashcards
1
Q
What are graphs?
A
- Consists of a FINITE:
- Vertices - Non-empty set of points
- Edges - set of lines
- Every edge is attaches at each end to a vertex
2
Q
What is an undirected graph?
A
- Non directed edge vertex pairs
- Simple graph:
- Undirected graph
- No loops (edge with vertex to itself)
3
Q
What is a directed graph?
A
- Directed edge vertex pairs
- NO multiple edges
- Loops are allowed
4
Q
What is a multigraph?
A
- Undirected graph
- More than one edge between a pair of vertices
- No loops allowed
5
Q
How do you describe a undirected graph
A
- e = unique edge
- x, y = vertices that e connects
- SO e = (x,y)
6
Q
How do you describe a directed graph?
A
- e = (x,y)
- x = origin vertices
- y = terminating vertex
7
Q
Describe this graph
A
8
Q
What is a complete graph?
A
9
Q
What is a connected graph?
A
10
Q
What is a vertex degree in a non directed graph?
A
11
Q
What is a vertex degree in a directed graph?
A
12
Q
What is a path?
A
13
Q
What is a circuit?
A
14
Q
What is a eulerian path?
A
- Eulerian Path = Path that visits every edge of a graph ONCE
15
Q
What is a eulerian circuit?
A
- Eulerian Circuit = Path that starts and end at the same vertex
- Vertices can be repeated in both an eulerian path and circuit
16
Q
What is a hamiltonian path?
A
- Hamiltonian path = path with every vertex of graph ONCE
17
Q
What is a hamiltonian circuit?
A
- Hamiltonian circuit = path that starts and ends at the same vertex
- Not all edges needs to be traverse in a hamiltonian circuit
18
Q
What is an adjacency matrix?
A
19
Q
What is an isomorphic graph?
A
- Two graphs are isomorphic if
- The vertices and edges are the same/ preserved in the other
- Can one graph be rearranged to look like the second one
