2 - Graphs and Networks Flashcards
Define graph.
Consists of points connected by lines.
Define weighted graph/network.
Number associated with each edge.
What are the points and lines called?
Nodes/vertices and arcs/edges.
Define vertex and edge set?
List of vertices/edges.
Define subgraph.
Graph whose vertices and edges belong to an original graph.
Define degree/valency of a vertex.
How many arcs are incident to it.
Define a walk.
A walk is a finite sequence of arcs such that the end vertex of one arc is the start vertex of the next.
Define a path.
A path is a (i) finite sequence of edges, such that (ii) the end vertex of one edge in the sequence is the start of the next and in which, (iii) no vertex appears more than once.
Define a trail.
A walk in which no edge is visited more than once.
Define a cycle.
A walk in which the end vertex of one edge is the start vertex of another and no vertex is visited more than once.
Define a Hamiltonian cycle.
A cycle including every vertex.
Define a connected graph/connected vertices.
All pairs of vertices connected by a path (but do not confuse with complete graph).
Define a loop.
An arc starting and finishing at the same vertex.
Define a simple graph.
No loops and at most one edge connecting any pair of vertices.
Define directed graph/digraph.
Edges have a direction associated with them.
Define Euler’s handshaking lemma.
In an undirected graph, the sum of the vertices’ degrees is 2x the number of edges and the number of odd vertices must be even or 0.
Define a tree.
A tree is a connected graph with no cycles.
Define a spanning tree.
A tree that connects all vertices.
Define a complete graph.
A graph where every vertex is connected by a single edge to all other vertices.
Define isomorphic graphs.
Same information but drawn differently.
Define an adjacency matrix.
A matrix with each entry showing the number of arcs joining corresponding vertices.
Define a distance matrix.
A matrix with each entry showing the weight of each arc.
