Brainscape's Knowledge GenomeTM

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


See full index

UNIT 5 > unit 5 dm > Flashcards

unit 5 dm Flashcards

1
Q

When are two vertices said to be adjacent/neighbours?

A

one edge between them atleast pic8

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

What is a null graph

A

no edges, all isolated vertexes

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

What is a trivial graph?

A

no edges and one vertices

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

What is a graph?

A

A collection of edges and vertices where the ordered pairs form edges

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

What does Graph G(V,E) represent?

A

V is an unempty set of vertices and E is a set of ordered pairs which represent edges

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

what does the therefore symbol represent (pic1)

A

null graph, 3 vertices

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

How is an edge represented?

A

a line, straight, curvy, long or short

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

Can the same graph be represented in diff ways? example?

A

pic2

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

How can graphs be classified?

A

finite: finite no. of edges and vertices
infinite: infinite no. of vertices

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

What are order and set and in which type of graph are the present?

A

In finite graph
OVSE
Order: no. of vertices
Set: no. of edges

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

(n,m) graph?

A

order -> n

size -> m

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

Graph(V,E) cardinality of V?

Set E cardinality?

A 
|V| = order
|E| = size
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Null graph with n vertices representation?

A

(n,0) graph

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

How are finite graphs classified?

A
  1. Directed
    direction associated with edge (ordered pair)
  2. Undirected
    no direction associated with edge (unordered pair)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are end vertices?

A

Vi and Vj are vertices joined by edge ek then edge vertices are Vi, Vj of ek
Symbolically pic3

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

How are vertices and edges represented?

A

Vertices: V1, v2 (subscript)
OR
A,B,Cā€¦

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

How are edges and edges represented?

A

e1, e2, e3..
or
AB, CD, ā€¦

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

Can edges intersect and not form a vertex at intersection point

A

yes

pic5

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

even if one vertix diff, denoted as

A

distinct end verticespic5

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

self loop?

A

same vertex as end vertices

pic5

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

loop?

A

edges with same end vertices
diff directions
pic5

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

parallel edges

A

edges with same end vertices
same direction
pic5

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

multiple edges

A

2 or more edges with same end vertix pic 4

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

simple graph

A

no loops, no multiple edges

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

loop free graph

A

no loops

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

multigraph

A

no loops, yes multiple edges

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

general graph

A

yes loops, yes multiple edges

28
Q

labeled graph

A

names are assigned to graph

29
Q

unlabeled graph

A

no names assigned to graph

30
Q

incidence

A

if there is an edge between A and B, A is incident on B pic 6
edge incident -> 2 vertices
vertix incident -> as many vertices

31
Q

degree of vertices? in which graph type?

A

undirected

no. of vertices incident on a vertix (edges between how many vertices)

32
Q

adjacent edge

A

non parallel edges with one common vertix

pic7

33
Q

complete/full graph

A

order >= 2 (vertices) at least one edge between all vertices
denoted by k subscript n
(n = vertices)
n = 5, Kuratowskiā€™s first graph pic9

34
Q

bipartite graph

A

pic10
split into 2 disjoint sets V1 and V2
every edge connects vertex from V1 to vertex in V2
None only within V1 or within V2

35
Q

complete bipartite

A

every v1 to every v2

pic 11, kurotowskis second graph

36
Q

is complete bipartite, complete graph? why

A

no edge between same bipartite

37
Q

How to check if bipartite?

A

assign 2 colors alternatively no adj same color

pic 12

38
Q

Types of undirected simple graphs

A

complete
cycle: every vertex degree = 2
pic13
wheel: vertex connected to every other vertex(all degree 3 except center = vertex no. - 1)pic14

39
Q

Types of graph

A

simple
multi
pseudo: self loops + maybe parallel edges
pic15

40
Q

Directed graph
G(V,E)
u and v?

A

collection of ordered pairs
V -> nonempty set of vertices
E -> ordered set of edges
starting ->u, ending -> v

41
Q

types of directed graphs

A

simple directed: no loops, no parallel edges
multi directed: parallel edges
pseudo/mixed directed:
directed + undirected edges

42
Q

Union of graphs

A

G(V1,E1) union G(V2,E2) G(V,E) where V = v1 union V2 etc

pic 16

43
Q

path/walk

A

seq of edges/vertices

44
Q

circuit/closed walk

A

same initial and end point

45
Q

simple path

A

each edge only once

46
Q

adjacency and incidence

A 
row,column = vertices
row = vertices column = edges
47
Q

deg(V) or d(v)

A

no. of edges join V vertices, loops 2x

48
Q

degree sequence of graph

A

all degrees in non-ascending order

49
Q

degree of graph

A

min deg(V) of graph

50
Q

isolated vertex

A

not end vertix (deg(V) = 0)

51
Q

pendant vertex

A

deg(V) = 1

52
Q

pendant edge

A

edge from pendant vertex

53
Q

regular graph of degree k/k-regular graph

A

all vertices, same degree, k

54
Q

3 regular graph aka

A

cubic graph

55
Q

Peterson graph

A

pic17

10 vertices, 15 edges

56
Q

3d hypercube Q3

A

pic 18

57
Q

k regular grapgh, 2^k vertices aka

A

k dimensional hypercube Qk

58
Q

handshaking property
why does it work?
why called handshake?
aka

A 
sum of all degrees = 2 * edges
each edge counted twice (at each end) 
even no. of hanshakes obvio
First Theorem of Graph theory
pic 19 -> math form
59
Q

Isomorphism

A

pic19 isomorphism reprsentation
f:V->Vā€™ (f onto 1-1)
{A,B}->E {f(A),f(B)}->Eā€™

SAME ADJ MATRIX(rearrange columns)
SAME DEGREES

Same order, same size -> not need isomorphic

60
Q

Subgraphs

A

g1 subgraph of g if:
all vertices and edges of g1 in g
edge in g1 same end vertices as g
g1 part of g

61
Q

Subgraph results

A

all graphs subgraph of itself
graph n vertices sub of complete kn
single vertex in G1 sub G
single edge + end verices sub G

62
Q

Spanning SubG

A

vertices in main

63
Q

Induced SubG

A

vertices and edges in main

64
Q

Edge/Vertex disjoint

A

both subs no common edge/no common edge and vertex

vertex disjoint -> edge disjoint

65
Q

complement of subG

A

G - subG(G1) = comp of G1 in G
G - G1 or G1(bar)
G1(bar) = G triangle G1

66
Q

walk classification

A

seq of vertixedge+
no. of edges -> length
vertix and edge more than once possible

67
Q

how many paths of length n

A

A = adj matrix -> A^n paths

UNIT 5 (20 decks)

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