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
It is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color.
Vertex Coloring
assigns a color to each edge so that no two adjacent edges share the same color.
Edge Coloring
is the minimum number of colors in a proper coloring of that graph. If chromatic number is r then the graph is r-chromatic.
Chromatic Number
