Brainscape's Knowledge GenomeTM

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


See full index

KCL Discrete Mathematics > Basic Graphs > Flashcards

Basic Graphs Flashcards

1
Q

Graph?

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

Simple graph?

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

Petersen graph?

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

d(v) is?

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

If graph G is simple then d(v) is?

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

Max degree of any vertex in G?

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

Minimum degree of any vertex in G

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

To show the two graphs are not isomorphic

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

Complete graph

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

Number of edges, in complete graph

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

Two vertices are adjacent if?

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

A walk from u to v

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

Trail

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

Path

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

Cycle

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

Graph G is connected if

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

A component of a graph G is

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

Disconnecting set

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

Cutset

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

If anyone of the edges in a cutset is retained

A

Graph stays connected

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

If a cut set consist of a single edge

A

The edge is called a cut edge, or a bridge

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

Separating set

A
28
Q

Separating set that consists of single vertex

A

Cut vertex

29
Q

Tree

A

Connected graph with no cycles

30
Q

Bipartite graph

A
31
Q

A graph is bipartite, if

A

And only if there are no cycles of odd length

32
Q
A
33
Q

Prove that G contains a cycle

A
34
Q

A connected graph is semi
Eulerian, if

A
  • And only if it has at most two vertices of odd degree

-There is a trial, which includes every edge of the graph

35
Q

A connected graph is eulerian if

A

and only if each vertex has even degree <=> the edge set of G can be partitioned into cycles <=> there is an eulerian trail

36
Q

A connected graph is semi eulerian if

A

And only if it has at most two vertices of odd degree

37
Q
A
38
Q

A connected graph is Hamiltonian, if

A
39
Q

Gabriel dirac’s, theorem

A
40
Q
A
41
Q

A forest?

A

Graph whose connected components are trees

42
Q

f(n,s)?

A

Number of forests , G, with n vertices and exactly s connected components

=n^(n-s-1)

43
Q

Number of trees of n vertices?

A

n^(n-2)

44
Q

eulerian trail?

A

a tour or a closed trail which includes every edge of G

45
Q

Degree of vertices of W_n?

A

One vertex of n-1 degree and all others degree 3

46
Q

Degree of vertices of C_n?

A

2 for all vertices

47
Q

Degree of vertices in K_n?

A

Every vertex has degree n-1

48
Q

A complete graph G with n vertices has how many edges?

A
49
Q

K_n,m

A

The complete bipartite graph where |V_1| = n and |V_2| = m and every vertex in V_1 is adjacent to every vertex in V_2

50
Q

And acyclic graph on n vertices has at most ? Edges

A

N-1

51
Q

Gabriel, dirac’s theorem

A
52
Q

Geometric graph

A

Any 2 e€E are disjoint or have one of their endpoints in common

(no crossing over)

53
Q

Euler’s formula

A

For any connected planar graph we have n - e + f = 2

f is # of faces

54
Q

The girth of a graph?

A

For a graph containing cycles, this is the length of the shortest cycle

55
Q

Bridge?

A

For a connected graph G, this is the urge to stops it from being connected when removed

56
Q

G be a connected planar graph on n vertices, if G is acyclic?

A

Then G has precisely n-1 edges

57
Q

G be a simple connected planar graph on n vertices, if G has girth atleast g?

A

Then G can have a most

58
Q

Let G be a connected planar graph with N vertices, n>=3, then?

A

G contains at most 3N-6 edges

59
Q

Two standard graphs that are not planar

A

K_5 K_3,3

60
Q

Edge contraction ?

A

Relive edge and merge all endpoint vertices into one vertex

61
Q

Edge expansion

A

Opposite of edge contraction, add new vertex and connect to end points of existing edge

62
Q

2 graphs are homeomorphic if

A

One can be obtained from the other by a sequence of edge, contractions and expansions

63
Q

Subdivision of a graph G

A

A graph that can be derived from G by a series of edge contractions

64
Q

A graph is planar iff?

A

And only if it does not contain a sub graph homeomorphic to K_5 or K_3,3 (Wagner)

65
Q

For a planar graph G drawn on a plane surface S, S’ is?

A

Surface obtained by removing all line segments in E

66
Q

A plane graph is

A

A graph G can be drawn in R^2 without crossings so edges only intersect in vertices

KCL Discrete Mathematics (9 decks)

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