General Flashcards Preview

MATH20902 Discrete Maths > General > Flashcards

Flashcards in General Deck (46)
1
Q

What is a Graph?

A

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
Q

What is an Undirected Graph?

A

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

3
Q

What is a Directed Graph?

A

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

4
Q

A bipartile graph?

A

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
Q

Define the degree of a vertex in an undirected graph

A

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

6
Q

Define a neighbour of vertex v

A

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

7
Q

Define a successor of a vertex V

A

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

8
Q

Define a predecessor for vertex v

A

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

9
Q

What does it mean for two graphs to be isomorphic?

A

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
Q

What is a Chromatic number?

A

The smallest K which G has been a K colouring

11
Q

Define the floor and ceiling of X

A

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
Q

Define a walk and it’s length?

A

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
Q

Define a trail

A

A trail is a walk where all the edges are distinct

14
Q

Define a path

A

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

15
Q

Define a cycle

A

A cycle is a path that includes 3 or more edges

16
Q

Define what it means for two verticies to be connected

A

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

17
Q

Define what it means for a graph to be connected

A

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

18
Q

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

A

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
Q

Define what it means for a to be accessible from b

A

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

20
Q

Define what it means for a graph to be strongly connected

A

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

21
Q

Define what it means for a graph to be weakly connected

A

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

22
Q

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

A

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

23
Q

Define what it means for graph to be acyclic?

A

A graph is acyclic if it has no cycles

24
Q

What is a Tree?

A

A tree is a connected acyclic graph

25
Q

What is a Forest?

A

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

26
Q

What is a leaf?

A

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

27
Q

What does it mean for a vertex to be isolated

A

if the vertex has a degree zero

28
Q

what is a Spanning Tree

A

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

29
Q

What is a root?

A

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

30
Q

What is an arborescence/ Directed Tree?

A

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

31
Q

What is a Spanning arborescence?

A

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

32
Q

What is a permutation?

A

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

33
Q

Define the fix(sigma)

A

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

34
Q

Define the sign(sigma)?

A

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
Q

What is a Spreg?

A

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
Q

What is an Eulerian Trail?

A

It is a trail which includes all edges once only

37
Q

What is an Eulerian tour/cycle?

A

It is a closed eulerian trail

38
Q

What does it mean for a Graph to be eulerian?

A

A multigraph is eulerian if it contains a eulerian tour

39
Q

What is an Hamiltonian Trail?

A

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

40
Q

What is an Hamiltonian tour/cycle?

A

Is a closed hamiltonian trail

41
Q

What does it mean for a graph to be Hamiltonian

A

A graph is Hamiltonian if it contains a hamiltonian tour

42
Q

What is an bridge

A

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

43
Q

What is a Planar Diagram ?

A

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
Q

Girth?

A

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

45
Q

What is a subdivision of a graph?

A

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
Q

What does it mean for two graphs to be homeomorphic?

A

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