Graphs and Networks Flashcards
(21 cards)
What is a graph?
a graph consists of points (vertices/ nodes) which are connected by lines (edges or arcs)
Well Done!
network/ weighted graph
a graph with a number associated with each edge (usually called its weight)
subgraph
a smaller graph (each of whose vertices and edges belong to the original graph) within a larger graph
degree/ valency/ order
the number of edges incident to a vertex
a walk
a route through a graph along edges from one vertex to the next
a path
a walk in which no vertex is visited more than once
a trail
a walk in which no edge is visited more than once
a cycle
a walk in which the end vertex is the start vertex and no other vertex is visited more than once
hamiltonian cycle
a cycle that includes every vertex
connected graph
a graph in which all the vertices are connected
a loop
an edge that starts and finishes at the same vertex
simple graph
one in which there are no loops and there is at most one edge connecting any pair of vertices
directed graph/ digraph
a graph whose edges have a direction associated with them (directed edges)
Euler’s handshaking lemma
in any undirected graph, the sum of the degrees of the vertices is equal to 2 times the number of edges. Consequently, number of odd nodes must be even
a tree
a connected graph with no cycles
spanning tree
a subgraph which includes all vertices of the original graph
complete graph
a graph in which every vertex is directly connected by a single edge to each of the other vertices
isomorphic graphs
graphs which show same information but may be drawn differently
adjecency matrix
each entry in this describes the number of arcs joing the corresponding vertices
distance matrix
entries represent the wright of each arc, not the number of arcs
