Graphs Flashcards
What does a graph consist of?
A Graph consists of vertices and edges.
What is a Trail?
A trail is a sequence of edges in which the end of one edge is the start of the next, and where no edge is repeated.
What is a Path?
A path is a trail with the further restriction that no vertex is repeated.
What is a Cycle?
A closed path.
What is a Connected Graph?
A graph is connected if there exists a path between every pair of vertices
What is a Simple Graph?
A simple graph is one that has no multiple edges or loops.
What is a Tree?
A tree is a simple connected graph with no cycles
What is the degree of a vertex?
The degree of a vertex is the number of edges that join it.
What is a Eulerian Graph and semi-Eulerian Graph?
A graph is Eulerian is it contains a closed trail that includes all the edges. It is semi-Eulerian if there is a trail that includes all the edges but it isn’t closed.
What is a Hamiltonian Graph?
A graph is Hamiltonian if it contains a cycle that visits all of the vertices exactly once.
What is a Planar Graph?
A graph is planar if it can be distorted in such a way that its edges do not cross.
What is Euler’s formula?
F-E+V=2
What is an Adjacency Matrix?
An Adjacency matrix shows the number of edges connecting any two vertices.
What is a Complete Graph?
A complete graph is one where every two vertices share exactly one edge (and where there are no loops)
What is the Complement of a simple graph?
Tee complement of a simple graph is obtained by adding in the edges necessary to make a complete graph, and then removing the original edges
