# Graph theory definitions

0.0 / 5

HideShow resource information

- Created by: Shannibean
- Created on: 09-05-18 14:04

Graph

A ----- is a network of dots ( vertices ) connected by lines ( edges ).

1 of 54

Degree of a vertex

The ------ -- - ------ is the number of edges connected to the vertex, counting any loop as connected twice

2 of 54

Multiple edges

Two or more edges linking the same pair of vertices are called ------- -----

3 of 54

Loops

An edge joining a vertex to itself is called a ----

4 of 54

Simple graph

A ------ ----- is one that has no loops or multiple edges.

5 of 54

Adjacency

Two vertices V and W of a graph are -------- if they are linked by an edge E.

6 of 54

Incidence

An edge E is -------- with the vertices it touches.

7 of 54

Isomorphism

Two graphs G and H are ---------- if H can be obtained by re-labeling the vertices of G.

8 of 54

Subgraph

A -------- H of a graph G is a graph all of whose vertices are of G and all of whose edges are of G

9 of 54

Degree Sequence

The ------ -------- of a graph G is the sequence obtained by listing the vertex degrees of G in ascending order, with repeats as necessary.

10 of 54

Walk

A ---- of length K is a succession of k edges. (for example a walk of length 3 could be denoted AB,BC,CD)

11 of 54

Trail

A ----- is a walk in which all the edges but not necessarily the vertices are different.

12 of 54

Path

A ----is a walk in which all the edges AND all the vertices are different.

13 of 54

Connectivity

A graph is --------- if there is a path between any two of its vertices. Otherwise it is disconnected.

14 of 54

Disconnected graph

Any ------------ ----- is the union of connected subgraphs, called components

15 of 54

Bridge

An edge in a connected graph is a ------ if it's deletion leaves a disconnected graph

16 of 54

Closed Walk

A ------ ---- in a graph is a walk that starts and ends at the same vertex.

17 of 54

Closed Trail

A ------ -----l is a closed walk in which all the edges are different.

18 of 54

Cycle

A ----- is a closed walk in which all the edges and all intermediate vertices are different.

19 of 54

Regular Graph

A graph is -------if it's vertices all have the same degree. A ------- ----- is r-regular if the degree of each vertex is r.

20 of 54

Tree

A ---- is a connected graph with no cycles.

21 of 54

Eulerian trail

A -------- ----- is a closed trail containing every edge of graph G

22 of 54

Eulerian Graph

A -------- ----- is a graph for which an Eulerian trail exists

23 of 54

Semi-Eulerian

A non Eulerian graph G is ----_-------- if there is an open trail containing every edge of G

24 of 54

Digraph

A directed graph ( or -------) D consists of a non-empty vertex set V and a finite family A of ordered pairs vw of vertices v,w that are elements of the set V , called arcs.

25 of 54

Simple Digraph

A digraph D is a ------ ------- if the arcs of D are all distinct and there are no loops.

26 of 54

Connected Digraphs

A digraph is connected if it's underlying graph is connected.

27 of 54

Strongly connected

A digraph D is -------- --------- if for any two vertices v,w that are a part of D there is a path from v to w on the digraph.

28 of 54

Orientability

A graph G is ---------- if each edge of G can be directed such that the resulting digraph is strongly connected.

29 of 54

Eulerian Digraph

A connected digraph D is -------- if there exists a trail containing every arc of D

30 of 54

Outdegree of a vertex

The --------- -- - ------ v is the number of arcs VW. The In-degree is the number of arcs WV.

31 of 54

Hamiltonian digraph

A digraph D is ----------- if there is a cycle that includes every vertex of D.

32 of 54

Semi-Hamilitonian

A digraph D is ----_----------- if there is a path that passes through every vertex of D

33 of 54

Tournament

A ---------- is a digraph in which any two vertices are joined by exactly one arc.

34 of 54

Forest

A ------ is a (not necessarily connected) graph with no cycles

35 of 54

Cycle rank

The number of edges removed in the procedure ( of removing cycles one edge at a time ) is the ----- ---- ( gamma ) of G.

36 of 54

Cutset Rank

The number of edges in a spanning tree is the ------ ---- (Xi) of G

37 of 54

Planar Graphs

A ------ ----- is a graph that can be drawn in the plane without crossings. ( may also be called a plane graph)

38 of 54

Crossing number

The -------- ------ cr(G) of a graph G is the minimum number of crossings that can occur when G is drawn in the plane

39 of 54

Homeomorphicity

Two graphs are ------------ if both can be obtained from the same graph by inserting additional vertices of degree 2 into it's edges.

40 of 54

Contractible

A graph G is ------------ to another graph H' if H' can be obtained by successively contracting edges of H. That is, by removing an edge and identifying it's end vertices

41 of 54

Faces

If G is a planar graph then any plane drawing of G divides the points on the plane that are not on G into regions- called -----. One of these faces is unbounded it is called the infinte face.

42 of 54

Face Degree

Let G be a connected planar graph, and F be any face of a plane drawing of G. Then the degree of F, written deg(F) is the number of edges of the boundary of face F

43 of 54

k-colourable

A graph G ( without loops ) is -_---------- if you can assign one of k colours to each vertex so that adjacent vertices have different colours

44 of 54

Chromatic number

If G is k-colourable but not (k-1)-colourable then we call G k-chromatic and it's --------- ------ ( chi of G ) is k

45 of 54

Map

A --- is a 3-connected plane graph

46 of 54

Colouring of maps

a map is k colourable if it's faces can be coloured with k colours such that no two faves with a common boundary edge have the same colour

47 of 54

k-edge-connectivity

Graph G is -_----_--------- if the smallest number of edges that must be deleted to disconnect G is >= k . ( i.e any cutset of G has >= k edges)

48 of 54

k-connectivity

Graph G is -_--------- if the smallest number of vertices that must be deleted to disconnect G is >= k

49 of 54

Network

A ------- N is a weighted digraph where each arc, a , is assigned a positive number ( psi(a)) called it's capacity.

50 of 54

A cut in a network

A --- -- - ------- is a set A of arcs such that each path from v to w includes and arc in A. A cut is a vw-disconnecting set.

51 of 54

Capacity of a cut

The -------- -- - --- is the sum of the capacities of the arcs in A

52 of 54

Minimum cut

A ------- --- is a cut with minimal capacity

53 of 54

Complete matching

A -------- -------- from A to B in a bipartite graph G(A,B) is a one to one correspondence between the vertices in A and a subset of vertices in B such that corresponding vertices are joined.

54 of 54

## Other cards in this set

### Card 2

#### Front

The ------ -- - ------ is the number of edges connected to the vertex, counting any loop as connected twice

#### Back

Degree of a vertex

### Card 3

#### Front

Two or more edges linking the same pair of vertices are called ------- -----

#### Back

### Card 4

#### Front

An edge joining a vertex to itself is called a ----

#### Back

### Card 5

#### Front

A ------ ----- is one that has no loops or multiple edges.

#### Back

## Similar Mathematics resources:

0.0 / 5

2.5 / 5

0.0 / 5

0.0 / 5

0.0 / 5

0.0 / 5

0.0 / 5

1.0 / 5

3.0 / 5

## Comments

Report