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

Define a walk

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

2

Define a Path

A walk in which no vertex is visited more than once

3

Define a Trail

A walk in which no edge is visited more than once

4

Define a Cycle

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

5

Define a Hamiltonian Cycle

A cycle that includes every vertex

6

Define a Loop

An edge that starts and finishes at the same vertex

7

Define a Simple Graph

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

8

Define a '2 vertices connected'

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

9

Define a Directed Graph (Digraph)

A graph where the edges are directed

10

Define Euler's handshaking Lemma

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

Define a Tree

A connected graph with no cycles

12

Define a Spanning tree

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

13

Define a Complete graph

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

14

Define Isomorphic graphs

Graphs which show the same information but are drawn differently

15

Define a Adjacency matrix

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

16

Define a Distance matrix

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

17

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

Vertices/Nodes
Edges/Arcs

18

Define Weighted Graph / Network

A graph that has a number associated with each edge

19

Define Subgraph

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

Define tour

Basically a Hamiltonian cycle plus visiting extra nodes if it wants