Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete Mathematics > Graph Theory > Flashcards

Graph Theory Flashcards

1
Q

Graph consists of ?

A

Vertices and edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Undirected graph?

A

Edges have no direction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

degree of a vertex

A

No. of vertices adjacent to it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

In degree of a vertex

A

No. of vertices directed towards a particular vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Out degree of a vertex

A

No. of vertices directed away from a particular vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Sum of degree=

A

2*no. of edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

In directed , sum of out degree=

A

Sum of in degree = no. of edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

outgoing edges denoted by

A

-

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

incoming edges denoted by

A

+

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Undirected graph types

A

Simple graph and Multigraph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Simple graph

A

No parallel edge, no self loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Multigraph

A

Parallel edges and self loop present

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Self loop degree=

A

2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

If n vertex simple graph, max and min degree

A

max-n-1
min-0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

If n vertex multigraph, max and min degree

A

max-infinite
min-0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Null graph

A

0 edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Complete graph

A

All edges in a simple graph
no. of edges=n(n-1)/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Min and max edges in a complete graph

A

both n(n-)/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

min and max edges in null graph

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

n-regular graph

A

all vertices have degree n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

for k regular graph no. of edges

A

e=(k*n)/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Complete graph with n vertices can be represented as n-1 regular graph

A

yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Every cycle graph is a

A

2-regular graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Cycle graph is not possible for

A

vertices less than or equal to 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Cycle graph Cn (2-regular graph with n vertices)

A

n vertices, n edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Wheel graph

A

Using Cn-1 graph and adding 1 vertex in middle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

For wheel graph

A

E=2*(n-1)

28
Q

Bipartite graph

A

Two groups m & n , no vertex b/w the members of same group

29
Q

In bipartite graph m U n =

A

V

30
Q

How to verify if graph is bipartite

A

BFS

31
Q

m intersection n for bipartite

A

empty set (phi)

32
Q

m can be anything but

A

empty set or phi

33
Q

n can be anything but

A

empty set or phi

34
Q

Which graph can never be bipartite

A

if it contains odd cycle

35
Q

Min. vertex for bipartite

A

2

36
Q

Min. edges for bipartite

A

0

37
Q

Complete bipartite graph

A

When all possible edges present in bipartite graph

38
Q

K2,4

A

Total edges = 8

39
Q

K m,n

A

edges= m.n
vertices=m+n

40
Q

Suppose you have 10 vertices, max edges complete bipartite =

A

when divided in half=5*5=25 edges

41
Q

Min. edges in bipartite graph

A

0

42
Q

Min. edges in complete bipartite graph with n vertices

A

(n-1).1

43
Q

Min edges in complete bipartite graph with m and n groups

A

m.n

44
Q

Max edges in bipartite graph

A

m.n

45
Q

Star graph edges with n vertices

A

n-1

46
Q

Planar graph

A

Draw graph w/o crossing any edges(can be represented in one plane)

47
Q

From which complete graph are all complete graphs non planar

A

K5

48
Q

Non planar requires least how many vertices

A

5 (one edge causes non planarity, if we remove becomes planar)

49
Q

In complete bipartite graph non planarity starts from

A

K3,3(one edge causes non planarity, if we remove becomes planar) so K3,4 K4,4 all are non planar

50
Q

Non planarity starts from min. vertices
min. edges

A

V-5 (K5)
E-9 (K3,3)

51
Q

A graph G is planar if and only if

A

it does not contain subgraph which is subdivision of K5 or K3,3

52
Q

Subdivision means

A

Same structure, only vertices added inside edges

53
Q

See question on copy

A
54
Q

Regions or faces

A

Every planar graph is divided into some regions

55
Q

Degree of a region

A

No. of edges it is bounded by

56
Q

Every edge is used twice in making regions

A

True

57
Q

Sum of degree of regions =

A

2*no. of edges

58
Q

See question

A
59
Q

Euler formula(Connected graph)

A

|V| + |R| = |E| + 2

60
Q

Euler formula(disconnected graph)

A

|V| + |R| = |E| + k + 1 (k-no. of connected components)

61
Q

For n vertices how many simple graphs possible

A

2^(n(n-1)/2)

62
Q

Average degree

A

Sum of degree/ no. of vertices

63
Q

Average degree bounds

A

Min degree <= Avg degree <= Max degree

64
Q

Average degree

A

2 |E| / |v|

65
Q
A

Discrete Mathematics (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions