Graph Theory Flashcards
What is a network?
A weighted graph (a graph with numbers or weights associated with the edges).
What is a subgraph?
A subgraph is a graph which is part of a larger graph.
What is the degree or valency or order of a vertex?
The number of arcs incident to that vertex.
What is a path?
A path is a sequence of edges, such that the end of one edge in the sequence is the start of the next edge, and in which no vertex appears more than once.
What is a walk?
A walk is a path where you are permitted to return to vertices more than once.
What is a cycle or circuit?
A path where the start and finish vertices are the same.
What is a connected graph?
A graph where there is a path between every pair of vertices.
What defines two vertices as being connected?
Two vertices are connected if there is a path between them.
What is a loop?
A loop is an edge that starts and ends at the same vertex.
What is a simple graph?
A simple graph is one in which there are no loops and no pair of vertices are joined by more than one edge.
What is a digraph?
A digraph is one where the edges of the graph have a direction associated with them.
What is a tree?
A tree is a connected graph with no cycles.
What is a spanning tree?
A spanning tree is a subgraph which includes all vertices of the original graph and is also a tree.
What is a bipartite graph?
A graph which consists of two set of vertices and where edges only connect vertices from the different sets.
What is a complete graph?
A complete graph is one where each vertex is directly connected by an edge to each other vertex in the graph.
