D1 Flashcards Preview

Maths > D1 > Flashcards

Flashcards in D1 Deck (13)
Loading flashcards...
1

Explain why a network cannot have an odd number of vertices of odd degree

Each edge contributes 2 to the sum of degree, hence this sum must be even.
Therefore there must be an even number of vertices of odd degree

2

Graph

consists of points (vertices) which are connected by arcs

3

Subgraph

a graph of graph G, each of whose vertices belong to G and each of whose edges belong to G

4

Degree/valency

of a vertex is the number of edges incident to it

5

Path

a finite sequence of edges, such that the end vertex of needle in the sequence is the start vertex of the next, and in which no vertex appears more than once.

6

Cycle (circuit)

A closed path (i.e. the end vertex of the last edge is the start vertex of the first edge)

7

Tree

a connected graph with no cycles

8

Spanning tree

a subgraph which included all vertices and is also a tree

9

Minimum spanning tree

a spanning tree such that the total length of its arcs is as small as possible

10

Complete graph

a graph in which each of the vertices is connected to every other vertex

11

Bipartite graph

consists of 2 sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set

12

Matching

the pairing of some or all of the elements of on set X, with some elements of a second set Y

13

Complete matching

if every member of X is paired with a member of Y