Graphs Flashcards
What is a graph?
Consists of a finite non-empty set of vertices and a set of lines connected
3 types of graph
Undirected graph, directed graph, multigraph
Completed graph
A simple graph where there is an edge between every pair of vertices
Connected graph
When there is an edge from every vertex to any other vertex
Degree
The degree of a vertex is the number of edges that are incident to the vertex
Total degree
The sum of all vertices (the twice number of edges)
In-degree of directed graph
the number of edges that are incoming on a vertex
Out-degree of directed graph
the number of edges that are outgoing from a vertex
Path
a sequence of vertices and edges you can trace without lifting pen off
Circuit
A path which starts and ends at the same vertex and may not contain repeated edges
Cycle
A circuit that contains no repeated vertices
Eulerian path
A path that visits every edge exactly once (vertex can be repeated)
Eulerian cicuit
An Eulerian path that starts and ends at the same vertex (vertex can be repeated)
Hamiltonian path
Includes every vertex exactly once
Hamiltonian circuit
A Hamiltonian path that starts and ends at the same vertex
