D1 Algorithms on graphs

Cards needed for D1 AS in Further Mathematics.

 

 

 

 

              Graph

1 of 32

 

 

A finite number of points (vertices or nodes) connected by lines (edges or arcs).

2 of 32

 

                

                Path

3 of 32

 

 

 

A finite sequence of edges such that the end vertex of one edge is the start vertex of the next.

4 of 32

 

 

 

              Cycle

5 of 32

 

 

 

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

6 of 32

 

 

 

     Hamiltonian Cycle

7 of 32

 

 

 

A cycle that passes through every vertex of the graph once, and only once, and returns to the start vertex.

8 of 32

 

 

 

       Eulerian Cycle

9 of 32

 

 

 

A cycle that includes every edge of the graph exactly once (all valencies must be even).

10 of 32

 

 

 

 

           Subgraph

11 of 32

 

 

 

A subset of vertices together with a subset of the edges

12 of 32

 

 

 

     Connected Graph

13 of 32

 

 

 

All pairs of vertices on the graph are connected       ( there is a path between each of them).

14 of 32

 

 

 

       Simple Graph

15 of 32

 

 

 

One in which there are no loops, i.e no edges with the same vertex at the end, and not more than one edge connecting any pair of vertices.

16 of 32

 

 

 

            Digraph

17 of 32

 

 

 

A graph in which the edges are directed (they have directions associated with them).

18 of 32

 

 

 

               Tree

19 of 32

 

 

 

 

              A connected graph with no cycles.

20 of 32

 

 

 

       Spanning Tree

21 of 32

 

 

 

A subgraph of a graph G that includes all the vertices of G and is also a tree

22 of 32

 

 

 

     Complete Graph

23 of 32

 

 

 

Every vertex is connected by an edge to every other vertex. Kn denotes a complete graph with n vertices.

24 of 32

 

 

 

 

       Bipartite Graph

25 of 32

 

 

Consists of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. Kr,s denotes a complete bipartite graph with r vertices in X and s vertices in Y.

26 of 32

 

 

 

        Planar Graph

27 of 32

 

 

 

No two edges meet one another, except at a vertex to which they are both incident, when the graph is drawn in a plane.

28 of 32

 

 

 

                Isomorphic Graph

29 of 32

 

 

 

Two graphs, G1 and G2 are isomorphic if they have the same number of vertices, and the degrees of the corresponding vertices are the same.

30 of 32

 

 

 

            Network

31 of 32

 

 

Each edge of the graph has a number (weight) associated with it. A network satisfies the triangle inequality if, for every triangle, no edge's weight exceeds the sum of the weights of the other two edges.

32 of 32

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Graphs and transformations resources »