Graphs and Networks

Question 1

what is different about graphs in discrete and decision maths compared to normal graphs?

Answer 1

they dont have axes

Question 2

what are the dots called

Answer 2

nodes or vertices

Question 3

what are the lines called

Answer 3

arcs or edges

Question 4

how do you find the degree (order) of a vertex?

Answer 4

how many edges there are at a vertex

Question 5

connected graph

Answer 5

possible to go from one vertex to another, go through other points

Question 6

what must happen for a graph to be formed?

Answer 6

the sum of the orders should be even

Question 7

loop

Answer 7

edges that start and finishes at the same vertex

Question 8

simple graph

Answer 8

no loop or multiple edges between two vertices

Question 9

complete graph

Answer 9

every vertex is connected to every other vertex

Question 10

what is the general formula of edges for a completed graph

Answer 10

0.5 x n x n-1

Question 11

digraph

Answer 11

at least one edge with a direction associated with it

Question 12

bipartite

Answer 12

nodes are in two distinct sets
every edge connected to a number of the first set to a member of the second set

Question 13

incidence matrix

Answer 13

shows the arrangement of edges in a graph

Question 14

trail

Answer 14

a sequence of joined edges such that no edge is repeated

Question 15

path

Answer 15

sequences of edges where the end vertex on one edge is the start of the next, no vertex visited more than one

Question 16

cycle

Answer 16

closed path

Question 17

tree

Answer 17

connected graph with no cycles

Question 18

spanning tree

Answer 18

subgraph which contains all vertices of original and is also a tree

Question 19

Eulerian graph

Answer 19

possible to make a trail that uses all edges once starting and ending at the same point

Question 20

Semi-Eulerian

Answer 20

ends at different vertex, but all edges have been used once, start and end on odd node