General Flashcards Preview

MATH20902 Discrete Maths > General > Flashcards

Flashcards in General Deck (46)
Loading flashcards...
1

What is a Graph?

A finite, nonempty set V, the vertex set along with set E, the edge set, whose elements e in E are pairs (a,b) with a,b in V

2

What is an Undirected Graph?

An undirected graph is a graph which the edge set consists of unordered pairs

3

What is a Directed Graph?

A Digraph/Directed graph is a graph in which pairs are ordered

4

A bipartile graph?

A graph is bipartile if it is a non empty edge set, and it’s vertex set can be decomposed into two disjoint nonempty subsets

5

Define the degree of a vertex in an undirected graph

The degree of a vertex is the no of edges that include the vertex

6

Define a neighbour of vertex v

In a graph a vertex u is a neighbour of a vertex v if (u,v)eE

7

Define a successor of a vertex V

In a directed graph a successor of a vertex v is a vertex u such that (v,u)eE

8

Define a predecessor for vertex v

In a directed graph a predecessor of a vertex v is a vertex u such that (u,v)eE

9

What does it mean for two graphs to be isomorphic?

Two graphs are said to be isomorphic if there exists a bijection a(v)-> v_2 such that (u,v)eE if and only if (a(u),a(v))eE

10

What is a Chromatic number?

The smallest K which G has been a K colouring

11

Define the floor and ceiling of X

Floor is the largest integer that is equal or smaller than X

The ceiling is the largest integer that is equal or larger than X

12

Define a walk and it’s length?

A set of edges is a walk if there exists a corresponding sequence of vertices

Its length is the number of edges in the sequence

13

Define a trail

A trail is a walk where all the edges are distinct

14

Define a path

A path is a trail in which all the vertices are distinct

15

Define a cycle

A cycle is a path that includes 3 or more edges

16

Define what it means for two verticies to be connected

In a graph two vertices are said to be connected if there is a walk between them

17

Define what it means for a graph to be connected

A graph is connected in which every pair of vertices is connected

18

Define what it means for a to be strongly connected to b

A and b in a digraph are strongly connected if there is a walk from a to b AND a walk from b to a

19

Define what it means for a to be accessible from b

In a discredited graph a vertex b is accessible from a vertex a if there is a walk a to b

20

Define what it means for a graph to be strongly connected

A directed graph is said to be strongly connected if all pairs of vertices are strongly connected

21

Define what it means for a graph to be weakly connected

A directed graph is weakly connected when one vertex ignore the directedness of the edges it becomes a connected undirected graph

22

Define what it means for vertex b to be accessible from vertex a

In a Digraph a vertex b is accessible from a if there is a walk from a to b

23

Define what it means for graph to be acyclic?

A graph is acyclic if it has no cycles

24

What is a Tree?

A tree is a connected acyclic graph

25

What is a Forest?

A forest is a graph who's connected components are trees

26

What is a leaf?

A vertex is a leaf in a tree if it has degree 1

27

What does it mean for a vertex to be isolated

if the vertex has a degree zero

28

what is a Spanning Tree

A subgraph of a graph is a spanning tree if it is a tree containing every vertex in v

29

What is a root?

A vertex in a digraph is a root of every other vertex if it is accessible to all

30

What is an arborescence/ Directed Tree?

A digraph is a DT/arborescence if it contains a root and if you ignore the directness it becomes a connected tree

31

What is a Spanning arborescence?

A subgraph of a Digraph is a SA if its an arborescence that contains all vertices in G

32

What is a permutation?

A permutation of n objects is a bijection from set {1,...,n}

33

Define the fix(sigma)

fix(sigma)={j | sigma(j)=j}

34

Define the sign(sigma)?

identity sigma =+1
If sigma is of a singular cycle length L then sign is (-1)^L-1
if sigma can be decomposed into k disjoint cycles then the sign ,L=sum(all cycles) (-1)^L-k

35

What is a Spreg?

A single predecessor graph is a directed graph in which each vertex other than the distinguished vertex V has exactly on predecessor while V has none

36

What is an Eulerian Trail?

It is a trail which includes all edges once only

37

What is an Eulerian tour/cycle?

It is a closed eulerian trail

38

What does it mean for a Graph to be eulerian?

A multigraph is eulerian if it contains a eulerian tour

39

What is an Hamiltonian Trail?

A hamiltonian trail is a trail which includes every vertex in V (once?)

40

What is an Hamiltonian tour/cycle?

Is a closed hamiltonian trail

41

What does it mean for a graph to be Hamiltonian

A graph is Hamiltonian if it contains a hamiltonian tour

42

What is an bridge

An edge is a bridge iff it G\e has more than one connected component

43

What is a Planar Diagram ?

A planar diagram for a graph G with Edge set E is a collection of simple curves that represent edges and have property g_i and g_j iff edges e_i and e_j iff the edges meet at their corresponding vertex

44

Girth?

If a graph contains at least one cycle then the girth is the length of the shortest cycle

45

What is a subdivision of a graph?

A subdisvion of a graph is a graph from by removing an edge and replacing it with a path, with each new vertex having a degree of 2

46

What does it mean for two graphs to be homeomorphic?

two graphs are said to be homoeopmorphic if they are isomorphic subdivisions of the same graph.