Modelling with Graphs and networks Flashcards
what is a graph?
no axis, just a diagram made up of edges and vertices
what are nodes/ vertices?
circles
what are edges /arcs?
lines connecting the dots
what is the degree/order of a vertex?
how many lines are coming out of that circle
what is a connected graph?
it is possible to go from any vertex to any other vertex
what is the relationship between the total order and the number of vertices?
- total order =12
- number of arcs = 6
total order will always be an even number
what is a loop?
an edge that starts and finishes at the same vertex
Order of a loop =2
what is a simple graph?
one with no loops and no multiple edges between two vertices
what is a complete graph?
one where every vertex is connected to every other vertex by an edge
How many arcs are in K(n)?
(n*n-1)/2
what is a digraph?
a graph where at least one edge has direction associated with it
what is a bipartite graph?
where the nodes are in two distinct sets. Each edge connects a emeber of the first set to a member in the second set. Points do not connect with any point within it’s own set
what is an incidence matrix?
shows the arrangment of edges between each node
what is isomorphism?
same number of nodes and orders of each node
between2 graphs
what is a trail?
a sequence of joined up edges, such that no edge is repeated
nodes can be used more than once
what is a path?
a sequenece of edges such that the end vertex on one edge is the dtart of the next. No vertex can be visited more than once
what is a cycle?
a closed path- where the first and last node are the same
what is a tree?
a simple connected graph with the minimum number of arcs. (If a single arc is removed it will no longer be a connected graph)
what is a spanning tree?
of graph G
a graph which contains all the vertcies of graph G and is also a tree
Q:
How many arcs are there in a tree with 10 nodes?
n-1
10-1=9
A simple connected graph G, has 8 vertices.
* what is the minimum number of edges that G could have?
* what is the maximum number of edges that G could have?
- minimum: 7
- maximum: (complete graph)
what is a eulerian/ traversible graph?
possible to make a trail that
* uses all edges once
* starts and ends at the same vertex
no nodes with odd degree
what is a semi eulerian/ traversable graph?
possible to make a trail
* uses all edges once
* starts and ends at difference vertices
will have exactly two odd nodes- start and end point
what is a network?
a value (weight) is added to each arc
Draw the incidence matrix for the following arrangement
