Topic 3 - Graphs and Networks
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/47
Earn XP
Description and Tags
term 2
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
48 Terms
What is a graph?
A visual representation of a network
What is a vertex?
A point representing an object in a network
What is an edge?
A connection between vertices
What is a loop?
An edge that starts and ends at the same vertex
What is the degree of a vertex?
The number of edges connected to the vertex
What is an arc?
A one-way edge
What is a subgraph?
A smaller section of a graph
What is a digraph?
A graph containing at least one arc
What is a simple graph?
No loops and no multiple edges
What is a complete graph?
Every vertex connected to every other vertex
What is a weighted graph?
Edges have values like distance or cost
What is a bipartite graph?
Two groups with no connections inside the same group
What is a planar graph?
A graph with no crossing edges
What is a face?
An enclosed region in a planar graph
Euler’s formula
V-E+F=2
What is an adjacency matrix?
A table showing connections between vertices
Undirected adjacency matrix rule
Matrix is symmetrical across diagonal
Simple graph adjacency matrix rule
0s on leading diagonal
Complete graph adjacency matrix rule
1s everywhere except leading diagonal
Degree rule from adjacency matrix
Add row or column values
Loop rule in adjacency matrix
Diagonal values count twice
Total edges from adjacency matrix rule
Add one side of leading diagonal
Multistage connection rule
Raise adjacency matrix to a power
Two-stage connection rule
M^2
What is a walk?
Can repeat edges and vertices
What is a trail?
No repeated edges but vertices can repeat
Why is a trail not a path?
Because vertices can repeat
What is a path?
No repeated edges and no repeated vertices
Why is a path also a trail?
Because if vertices do not repeat then edges cannot repeat
What is a circuit?
A closed trail
Why is a circuit not always a cycle?
Because vertices can repeat
What is a cycle?
A closed path
Why is a cycle stricter than a circuit?
Because no vertices or edges can repeat
What is a connected graph?
Every vertex can be reached from another vertex
What is a bridge?
An edge that disconnects the graph if removed
What is a Hamiltonian graph?
Visits every vertex exactly once in a cycle
Why is a Hamiltonian graph not Eulerian?
Hamiltonian focuses on vertices not edges
What is a semi-Hamiltonian graph?
Visits every vertex exactly once in an open path
Why is a semi-Hamiltonian graph not Hamiltonian?
Because it does not end where it started
What is a Eulerian graph?
Uses every edge exactly once in a closed trail
Why is a Eulerian graph not Hamiltonian?
Eulerian focuses on edges not vertices
Eulerian graph rule
All vertices even degree
What is a semi-Eulerian graph?
Uses every edge exactly once in an open trail
Semi-Eulerian graph rule
Exactly two odd vertices
Why is a semi-Eulerian graph not Eulerian?
Because it starts and ends at different vertices
What is the shortest path?
The path with the smallest total weight
Shortest path algorithm start rule
Label starting vertex 0
Shortest path algorithm rule
Keep smallest possible total at each vertex