Maths apps- Graph theory definitions

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/44

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

45 Terms

1
New cards

Graph

Diagram showing lines connecting points

2
New cards

Vertex

One of the points in a graph

3
New cards

Edge

One of the connecting lines in a graph

Two vertices are adjacent if they are joined by an edge

4
New cards

Multiple edges

Two or more edges that connect the same vertices

5
New cards

Loop

An edge that joins a vertex directly to itself

6
New cards

Simple graph

One that has no loops or multiple edges

7
New cards

Degree of a vertex

The number of edges connected to that vertex (A loop is considered to be connected to its vertex twice)

The sum of the degrees in a graph will always be even since every edge joins two vertices

8
New cards

Directed graph

One in which all the edges have a direction- in this case the edges are usually called arcs

9
New cards

For an undirected graph

The sum of the degrees of the vertices equals twice the number of edges

10
New cards

Adjacency matrix

Shows the number of edges that join adjacent vertices

For a given network shows the number of one-step routes between the vertices eg M

M² gives number of two-step routes, M³ 3-step routes and so on

11
New cards

Symmetric about the leading diagonal

Means that you can go along each edge in either direction

12
New cards

Directed graph adjacency matrix

Shows the number of edges from one vertex to another, in that particular direction

13
New cards

Planar graph

A graph that can be drawn in the plane

A planar graph can always be drawn so that no two edges cross

14
New cards

Weighted graph

A graph in which each edge is labelled with a number used to represent some quantity associated with the edge

15
New cards

Connected graph

One in which there is a path between each pair of vertices, ie. a way of getting from each vertex to each other vertex via one or more edges

16
New cards

Bridge

An edge in a connected graph that, if removed, leaves a graph disconnected

17
New cards

Complete graph

A simple graph in which every vertex is joined to every other vertex by an edge. The complete graph with n vertices is denoted Kn.

18
New cards

A complete graph with n vertices

Has n(n-1) / 2 edges

19
New cards

Subgraph

A graph that consists of some (though not necessarily all) of the vertices and edges in the original graph

20
New cards

Bipartite graph

A graph whose set of vertices can be split into two distinct groups in such a way that each edge of the graph joins a vertex in the first group to a vertex in the second group

Every subgraph of a bipartite graph is also bipartite

21
New cards

Complete bipartite graph

A bipartite graph where every vertex of the first set is connected to every vertex of the second set

22
New cards

Number of edges in a complete bipartite graph

Is m x n, where m is the number of vertices in the first group and n is the number of vertices in the second group

23
New cards

Bipartite graph test

Start at any vertex and colour it eg white, then colour any vertex connected to it black, then move to hose vertices and continue to process through the network until all vertices are either white or black. If any edge has two white or two black vertices at its ends, then the graph is not bipartite. If every vertex has one white and one black vertex at its ends, then the graph is bipartite

24
New cards

Faces

Regions in a graph bounded by the edges, including the outer infinitely large region

25
New cards

Euler’s rule

States that for a connected planar grate, v + f — e = 2, where v is the number of vertices, f is the number of faces and e is the number of edges

26
New cards

Walk

Any route in a graph from one vertex to another vertex along the connecting edges

Doesn’t have to include all the vertices/edges, can repeat vertices/edges

27
New cards

Open walk

A walk that starts and finishes at different vertices

28
New cards

Closed walk

A walk that starts and finishes at the same vertex

29
New cards

Length of a walk

The number of edges it includes

30
New cards

Trail

A walk in which no edge is repeated

31
New cards

Open trail

Trail that starts and finishes at different vertices

32
New cards

Closed trail/circuit

A trail that starts and finishes at the same vertex

33
New cards

Path

A walk in which all of the edges and all the vertices are different (a path may start and finish at the same vertex)

34
New cards

Open path

A path that starts and finishes at different vertices

35
New cards

Cycle/closed path

A path that starts and finishes at the same vertex

36
New cards

Eulerian

A connected graph that has a closed trail (starts and ends at the same vertex) that includes every edge once and once only

May include repeated vertices

Have no vertices of odd degree- each vertex must be of even degree

37
New cards

Semi-Eulerian

If there is an open trail that includes every edge once only

Two vertices must be of odd degree, all others even

Can only be traversed by starting at one of the odd vertices and finishing at the other

38
New cards

Eulerian trail

A walk with no repeated edges that includes every edge in a graph

39
New cards

Open/Semi Eulerian trail

Will only exist if graph has exactly two vertices of odd degree

40
New cards

Closed Eulerian trail

A walk with no repeated edges that includes every edge in a graph and starts and finishes at the same vertex

Will only exist if graph has all vertices of even degree

41
New cards

Hamiltonian path

A path that includes every vertex in a graph once only

A path cannot have repeated edges
Does not have to visit every edge

42
New cards

Hamiltonian cycle

A cycle that includes each vertex in a graph (except the first) once only

43
New cards

Hamiltonian graph

A graph that contains a Hamiltonian cycle

44
New cards

Semi-Hamiltonian graph

A graph that contains a Hamiltonian path but not a Hamiltonian cycle

45
New cards

Graph will not be hamiltonian

If it contains a bridge