Graph types
Graph Features
Walk/Trail/Path/Cycle
Eularian/Hamiltonian
Weighted/Spanning Trees
100
a graph that is fully connected, no separate parts
connected graph
100
a dot on the graph
vertex
100
starts and ends at same vertex, no edge repeated
cycle
100
a graph that has a closed cycle that uses every edge and has even degree vertices
Eularian Graph
100
a graph that has numbers on its edges
Weighted Graph
200
How many edges in this network?
9
200
a line on the graph that connects vertices
edge
200
no edges or vertices repeated
path
200
A graph that has an open path that visits every vertex once
Semi Hamiltonian Graph
200
a subgraph that uses all vertices as a tree
Spanning Tree
300
How many vertices in this network?
6
300
an area of a graph that can be inside or outside
face
300
No edge repeated but can repeat vertex
Trail
300
a graph that has an open trail that uses every edge and has exactly 2 odd degree vertices
Semi Eularian Graph
300
a spanning tree that has the smallest possible length/weight/value of the edges.
minimum spanning tree
400
What makes this network weighted?
The numbers on the edge.
400
an edge that goes from a vertex back to itself
loop
400
can repeat vertices or edges
walk
400
a graph that has a closed cycle that goes through every vertex once
Hamiltonian Graph
400
The process where you select a vertex and then select every smallest edge one by one to connect the vertices into a minimum spanning tree
Prims Algorithm
500
What is the shortest path from A to E?
A-B-D
500
the number of edges coming off a vertex
degree
500
another name for a closed path
cycle
500
Can a square complete graph be described as any of these:
a Eularian, Semi Eularian, Hamiltonian or Semi Hamiltonian?
Hamiltonian and Semi hamiltonian (Not eularian or semi Eularian)
500
Determine the value of the minimum spanning tree of this network.
24