Modelling with algorithms: networks Flashcards
In discrete mathematics, what is a graph?
a graph is a set of lines(called arcs or edges) connecting points(nodes or vertices)
What is a loop?
A loop is an arc with the same node at both ends.
What does multiple arcs refer to?
when two nodes are connected by more than one arc
What is order/degree?
The order/degree of a node is calculated as the number of arcs incident to it.
What is an Incidence matrix?
A table which represents a graph, by showing the number of arcs that directly connect one node to another
Two nodes that directly connect are said to be?
adjacent
what does the sum of each column or row in the matrix give?
it shows the ORDER of each relevant node
What is a Connected graph?
A graph in which each node is directly or indirectly connected to every other node (basically there is only one shape, not several)
What is a simple graph?
a graph with no REPEATED arcs or loops
What is a complete graph?
A graph in which every node is connected directly to every other node
Formula for complete graph?
K = n(n-1) / 2
n is the number of nodes, K is number of arcs
What is a tree?
A simple connected graph with no cycles, and the minimum number of arcs , (n - 1)
formula for tree
k = n -1
k is arcs, n is nodes
bipartite and digraph
bipartite is when graphs are in distinct sets and each node connects to at least one node in the other set
digraphs have a directed node with an arrow
What is a trail?
A sequence of joined edges where no edge is gone over more than once
what is a path?
a sequence of edges where the vertex on the end of one edge is the start of the next, and no vertexes are repeated(besides perhaps first or last)
what is a spanning tree?
A subgraph of a graph which is a tree and has the same vertices
What is the formula for the maximum number of trees that can be made
m = n -2
n is number nodes, m is number of graphs
What is a eulerian graph? What condition is there on the nodes?
a graph on which a trail that uses all edges once can be make, that starts and ends on the same vertex .
For a graph to be eulerian, there can be no nodes with odd degree
What is a se,i eulerian graph? what conditions does it have on the nodes?
is a graph where a trail can be made that uses all edges ones, but starts and ends at different vertices
there can be only EXACTLY two nodes with odd degree
