Definitions Flashcards
Subgraph
A subgraph is part of a graph
Graph
A graph consists of vertices (nodes) which are connected by edges (arcs)
Weighted graph
A graph where there is a number associated with each edge (arc)
Degree or valency
The number of edges (arcs) incident to a vertex (node)
Path
A finite sequence of edges where the end vertex (node) of an edge (arc) is the start vertex of the next edge and where no vertex appears more than once
Walk
A path where you can return to vertices (nodes) more than once
Trail
A walk with no repeated edges (arcs)
Cycle/ circuit
A closed path, the end vertex (node) of the last edge (arc) is the start vertex of the first node
Connected
Two vertices (nodes) are connected if there is a path between them
Connected graph
A graph where all of it’s vertices (nodes) are connected (have a path between them)
Loop
An edge (arc) that starts and finished at the same vertex (node)
Simple graph
A graph where there are no loops and does not have more than once edge (arc) connecting any pair of vertices (nodes)
Directed edge
An edge (arc) that has an associated direction
Digraph
A graph where edges (arcs) have a direction associated with them
Tree
A connected graph with no cycles
