Graph Definitions Flashcards
What is a Graph?
Vertices connected by edges.
What is a subgraph?
A separate part of a graph
What is a weighted graph?
A graph with numbers associated with the edges
What does valency mean?
The number of edges incident to a vertex
What is a path?
The finite sequence of edges where no vertex appears more than once
What is a walk?
A path in which you are allowed to return to vertices more than once
What is a cycle?
A closed path where the first vertex is the last vertex
How are two vertices connected?
If there is a path between them
How is a path connected?
If all the vertices are connected
What is a loop?
An edge that starts and finishes at the same vertex.
What are the qualities of a simple graph?
It has no loops and no more than one edge connects a pair of vertices
What is a digraph?
A graph where the edges have directions associated with them
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A sub graph which is also a tree.
What is a bipartite graph?
Vertices in x only join to vertices in y. Not to vertices in the same set
