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
What is Subdivision?
A Subdivision of a graph is obtained by inserting a new vertex into an edge
What is a Bipartite Graph?
A Bipartite graph contains two sets of vertices, with edges joining a vertex in one set to a vertex in the other.
What does it mean for Graphs to be Isomorphic?
Two graphs are isomorphic if one can be distorted in some way to produce the other
What is Kuratowski’ Theorem?
Kuratowski’s theorem says that a graoh is non-planar if and only if it contains a subgraph that is a subdivision of either K₃,₃ or K₅ .
What does it mean for graphs to be planar?
A graph is said to be planar if it can be distorted in such a way that its edges do not cross
