Modelling with algorithms: networks

Question 1

In discrete mathematics, what is a graph?

Answer 1

a graph is a set of lines(called arcs or edges) connecting points(nodes or vertices)

Question 2

What is a loop?

Answer 2

A loop is an arc with the same node at both ends.

Question 3

What does multiple arcs refer to?

Answer 3

when two nodes are connected by more than one arc

Question 4

What is order/degree?

Answer 4

The order/degree of a node is calculated as the number of arcs incident to it.

Question 5

What is an Incidence matrix?

Answer 5

A table which represents a graph, by showing the number of arcs that directly connect one node to another

Question 6

Two nodes that directly connect are said to be?

Answer 6

adjacent

Question 7

what does the sum of each column or row in the matrix give?

Answer 7

it shows the ORDER of each relevant node

Question 8

What is a Connected graph?

Answer 8

A graph in which each node is directly or indirectly connected to every other node (basically there is only one shape, not several)

Question 9

What is a simple graph?

Answer 9

a graph with no REPEATED arcs or loops

Question 10

What is a complete graph?

Answer 10

A graph in which every node is connected directly to every other node

Question 11

Formula for complete graph?

Answer 11

K = n(n-1) / 2
n is the number of nodes, K is number of arcs

Question 12

What is a tree?

Answer 12

A simple connected graph with no cycles, and the minimum number of arcs , (n - 1)

Question 13

formula for tree

Answer 13

k = n -1
k is arcs, n is nodes

Question 14

bipartite and digraph

Answer 14

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

Question 15

What is a trail?

Answer 15

A sequence of joined edges where no edge is gone over more than once

Question 16

what is a path?

Answer 16

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)

Question 17

what is a spanning tree?

Answer 17

A subgraph of a graph which is a tree and has the same vertices

Question 18

What is the formula for the maximum number of trees that can be made

Answer 18

m = n -2
n is number nodes, m is number of graphs

Question 19

What is a eulerian graph? What condition is there on the nodes?

Answer 19

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

Question 20

What is a se,i eulerian graph? what conditions does it have on the nodes?

Answer 20

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