Decision: Graphs and Networks: Definitions Flashcards Preview

A Level Further Maths > Decision: Graphs and Networks: Definitions > Flashcards

Flashcards in Decision: Graphs and Networks: Definitions Deck (20)
Loading flashcards...
1
Q

Define a walk

A

A route through a graph along edges from one vertex to the next

2
Q

Define a Path

A

A walk in which no vertex is visited more than once

3
Q

Define a Trail

A

A walk in which no edge is visited more than once

4
Q

Define a Cycle

A

A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

5
Q

Define a Hamiltonian Cycle

A

A cycle that includes every vertex

6
Q

Define a Loop

A

An edge that starts and finishes at the same vertex

7
Q

Define a Simple Graph

A

A graph in which there are no loops and there is at most one edge connecting any pair of vertices

8
Q

Define a ‘2 vertices connected’

A

Two vertices are connected if there is a path between them.

9
Q

Define a Directed Graph (Digraph)

A

A graph where the edges are directed

10
Q

Define Euler’s handshaking Lemma

A

In any undirected graph, the sum of the degrees pf the vertices = 2* the number of edges. As a consequence the number of odd nodes must be even = Euler’s handshaking Lemma

11
Q

Define a Tree

A

A connected graph with no cycles

12
Q

Define a Spanning tree

A

A spanning tree of a graph is a subgraph which includes all the vertices of the original graph and is also a tree

13
Q

Define a Complete graph

A

A graph in which every vertex is directly connected by a single edge to each of the other vertices

14
Q

Define Isomorphic graphs

A

Graphs which show the same information but are drawn differently

15
Q

Define a Adjacency matrix

A

A matrix in which every entry describes the number of arcs joining the corresponding vertices

16
Q

Define a Distance matrix

A

A matrix in which the entries represent the weight of each arc

17
Q

A graph consist of points [ ] which are connected by lines [ ]

A

Vertices/Nodes

Edges/Arcs

18
Q

Define Weighted Graph / Network

A

A graph that has a number associated with each edge

19
Q

Define Subgraph

A

A graph, each of whose vertices belongs to the original graph and each of whose edges belong to the original graph. It is part of the original graph

20
Q

Define tour

A

Basically a Hamiltonian cycle plus visiting extra nodes if it wants