Modelling with graphs and networks 1: Working with graphs Flashcards
What is a graph?
A graph is a set of nodes (or vertices) together with a set of arcs (or edges).
What is a loop?
A loop is an edge with the same vertex at both ends.
What is the order of a vertex?
The order (or degree) of a vertex is the number of edges incident on it.
What is an incidence matrix?
A matrix that represents a graph/network: (0 1 2 0 0) (1 2 1 0 0) (2 1 0 0 0) (0 0 0 0 1) (0 0 0 1 0)
e.g. first point is how many connections from A to A
What is a connected graph?
A connected graph is one in which every vertex is joined, directly or indirectly to each of the other vertices
What is a simple graph?
A simple graph is a graph with no loops and no ‘repeated’ edges.
What is a simply connected graph?
A simply connected graph is a graph that is both simple and connected.
What is a tree?
A tree is a simply connected graph with the minimum possible number of arcs
How many edges does a tree on n vertices have?
A tree on n vertices has n-1 edges
What is a complete graph
A complete graph is a simply connected graph with the maximum possible number of arcs
How many edges does a complete graph on n vertices have?
A complete graph on n vertices has (n(n -1))/2 edges.
What is a digraph?
A digraph is a graph where some of the arcs are directed. The incidence matrix for a digraph will usually not be symmetric about the leading diagonal.
What is a bipartite graph?
A bipartite graph is one where the vertices partition into two sets and edges cannot join vertices that are in the same set.
What is a network?
A network is a graph with weighted arcs.
