NETWORKS

Question 1

What is Euler’s formula for

Answer 1

Planar graphs

Question 2

Bridge

Answer 2

edge
when removed will make graph disconnected

Question 3

Faces

Answer 3

inside + 1 outside

Question 4

Connected graph

Answer 4

all vertices connected to an edge

Question 5

degree

Answer 5

no. edges connected to a single vertex
loops = x2
even/odd degrees

Question 6

Degenerate/null graph

Answer 6

all lonely dots

Question 7

Isolated vertex

Answer 7

lonely dot
degree = 0

Question 8

Simple graph

Answer 8

no loops/multiple edges
sum of degree = 2x no. edges

Question 9

Complete graph

Answer 9

all vertices connected to all other vertices
no. edges = n(n-1) / 2 n = no. vertices

Question 10

Bipartite graph

Answer 10

set of vertices able to be split on two sides
same side vertices do not connect
vertices on one side connect with vertices on other side
colouring method- alternate colours perfectly = bipartite

Question 11

Complete bipartite graph

Answer 11

every vertex on one side connected to all vertices on other
edges = no. edges on each side multiplied

Question 12

Subgraph

Answer 12

some original vertices but not all

Question 13

Length

Answer 13

sum of vertices - 1

Question 14

Planar graph

Answer 14

connected graph
can be redrawn to have no crossing edges
K5 = never planar

Question 15

Plane drawing

Answer 15

Redrawn planar graph

Question 16

Adjacency matrix

Answer 16

symmetrical about leading diagonal
1 step = N1
2 step = N^2 - ways to travel from 1 to other via another point
1 or 2 step- N + N^2 - ways to travel from 1 to other direct or via another point

Question 17

Walk

Answer 17

sequence with both repeated edges + vertices

Question 18

Trail

Answer 18

No repeated edges

Question 19

Path

Answer 19

No repeated edges or vertices

Question 20

Open

Answer 20

Starts + ends at different vertices

Question 21

Closed

Answer 21

Starts + ends at same vertex

Question 22

Eulerian

Answer 22

All even vertices
closed trail

Question 23

Semi-eulerian

Answer 23

2 vertices odd
starts+ ends at odd points
open trail

Question 24

Hamiltonian

Answer 24

closed path
does not need to go through all edges

Question 25

Semi-Hamiltonian

Answer 25

open path
does not need to go through all edges

Question 26

Circuit

Answer 26

closed trail

Question 27

Cycle

Answer 27

closed path