Graph Theory Flashcards
Studies network and connectivity.
Graph Theory
A study that has helped us build the internet.
Graph Theory
Used to represent networks of communication, data organization, computational devices, the flow of computation, etc.
Graphs
What is the birth of Graph Theory attributed to?
Seven Bridges of Konigsberg
Who is the mathematician attributed to the birth of Graph Theory?
Leonhard Euler
The year Graph Theory was introduced is?
1736
What is a set of nodes of vertices linked by edges?
Graph
What are the main points of a graph?
Nodes/Vertices
What do you call the arcs or branches of a grapah?
Edges
What term is used when attributes are given to the vertices and/or edges?
Network
What do you call a graph whose edges are not all bidirectional?
Directed/Diagraph
What do you call a graph where no edge is bidirectional?
Undirected
A sequence of distinct edges that join two nodes through other nodes.
Path
The number of edges in a path.
Length of a Path
A path that begins and ends at the same vertex.
Circuit
What do you call it if a path connects a node to itself?
Cycle
Cycles with length one.
Loops
What do you call it if two distinct nodes are linked by at least one path?
Connected
A graph that has no loops and has no edges that repeat.
Simple Graph
A connected graph that has no cycles.
Tree
A graph where it is possible to find a route that starts from one vertex, traverses every edge exactly once, and ends at the starting veretex.
Euler Graphs
Route of Euler Graphs that are not unique.
Eulerian trail.
A graph wherein it is possible to find a route that starts with one vertex, visits every vertex exactly once along incident edges, and ends at the starting vertex.
Hamiltonian Graphs
Route of Hamiltonian Graphs.
Hamiltonian Cycle
A kind of tree that minimizes the lengths (or “weights”) of the edges of the tree.
Minimum Spanning Tree
Equation of the cost of the spanning tree.
Sum of the weights of all the edges in the tree
Finds the “shortest” route from one vertex to another.
Shortest Path Algorithm
