Networks

Question 1

Edges

Answer 1

The sets of lines that join vertices

Question 2

Vertices

Answer 2

A set of points

Question 3

Loop

Answer 3

An edge that starts and ends at the same vertex

Question 4

Multiple edges

Answer 4

When two or more edges connect the same two vertices

Question 5

Adjacent vertices

Answer 5

When two vertices are connected by a path that only involves one edge

Question 6

Degree of vertex

Answer 6

The number of edges connecting to the vertex

Question 7

Sum of degrees

Answer 7

Formula that says if you add up of the degrees of the vertices in a graph, the result is twice the number of edges in the graph

Question 8

Isolated vertice

Answer 8

A vertice that is not connected to any other vertices. It has a degree of 0

Question 9

Null graph

Answer 9

A graph made up of multiple isolated vertice, has no edges

Question 10

Regular graph

Answer 10

A graph in which each vertice has the same number of degrees

Question 11

Weighted graph

Answer 11

Graphs that have amounts, distances or some information on each edge

Question 12

Subgraph

Answer 12

A portion of an existing graph

Question 13

Trivial graph

Answer 13

A graph containing one single isolated vertice

Question 14

Simple graph

Answer 14

An undirected, unweighted graph with no loops or multiple edges

Question 15

Connected graph

Answer 15

A graph where every vertex is connected to every other vertex. (Meaning travelling across several edges is applicable)

Question 16

Complete graph

Answer 16

Simple graphs in which every vertice is connected to every other vertice by, in each case, a single edge

Question 17

Planar graph

Answer 17

A graph where no edges cross over each other

Question 18

Euler’s formula

Answer 18

vertices-edges+faces=2

Question 19

If a graph doesnt fit euler’s formula?

Answer 19

There is not a connected, planar network with those properties

Question 20

What statement defines a connected planar graph?

Answer 20

Connected planar graphs have an even number of vertices with odd degrees

Question 21

Bipartite graph

Answer 21

A graph whose vertices can be divided into 2 groups such that each edge connects a vertex from one group to a vertex in another. Vertices in a group are never connected to other vertices in that group

Question 22

Matrix properties

Answer 22

• A loop is counted as one edge
• The sum of the row entries gives the degree of the vertex corresponding to that row. For any vertex containing a loop, 1 must be added as a loop is counted as two edges in the context of the degree of a vertice

Question 23

Eulerian graph

Answer 23

It has a closed trail (Starts and finishes at same vertices) that includes every edge once only. The graph must be connected and have all vertices of an even degree

Question 24

Semi-eulerian

Answer 24

It has an open trail (Starts and finishes at different vertices) that includes every edge once only. The graph must be connected and have two vertices of an odd degree

Question 25

Where do semi-eulerian trails start and finish

Answer 25

Must start at one of the odd vertices and finish at another

Question 26

Hamiltonian cycle vs path

Answer 26

Path: Goes to every vertex Cycle: Goes to every vertex and starts and ends at the same vertex