graph theory Flashcards
He presented the solution to the problem before the Russian Academy. He explained why crossing all seven bridges without crossing a bridge twice was impossible.
Leonard Euler
It is a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices.
graph
A is an edge connecting a vertex to itself.
loop
If two vertices are connected by more than one edge, these edges are called
multiple edges.
A graph with no loops and no multiple edges is called a
simple graph.
It is an edge that when you remove makes the
graph disconnected.
Bridge
It is an alternating sequence of vertices and edges. It can be seen as a trip from one vertex to another using the edges of a graph.
Path
If a path begins and ends with the same vertex
it is a closed path or a circuit or cycle.
Two vertices are adjacent if there is an edge joining them.
It is a graph that has an edge connecting every pair of
vertices.
complete graph
It is a connected graph in which every possible edge is drawn between vertices. It should not contain multiple edges.
complete graph
A graph that has an Euler circuit is called
Eulerian
It is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which forms a tree that includes every vertex
Prim’s Algorithm
It is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which form a tree that includes every vertex and has the minimum sum of weights among all the trees that can be formed from the graph
Kruskals algorithm
A graph is _____ if it can be drawn in such a way that no edges cross.
planar
