Brainscape's Knowledge GenomeTM

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


See full index

Graph Theory > Module 1 > Flashcards

Module 1 Flashcards

1
Q

Graph

A

Let V be a finite non empty set and E be the subset of VxV then G=(V,E) is called a Graph, where V is the set of vertices and E is the set of Edges

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

Trvial Graph

A

graph with a single vertex

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

Null(empty Graph)

A

No edges

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

Isolated Vertex

A

a Vertex that is not adjacent to any other vertex

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

Parallel edge

A

in a graph G=(v,e) if more than one edge is associated with a pair of vertices than these edges are called parallel edge

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

Order and Size

A

If G=(V,E) be a finite grapgh where V(G) denotes the number of vertices in G and is called Order of that graph and E(G) denotes number of Edges in G and is called the size of G
ie
order = number of vertices
size = number of edges

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

Simple Graph

A

Graph with no self loops or parallel edges

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

Incidence on graph

A

When a vertex vi is the end vertex of edge ei then ei and vi are said to be incident with each other

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

adjacent vertex

A

two vertices are said to be adjacent if they are the end vertices of the same edge

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

degree of a vertex

A

no of edges connected to it (self loop is counted twice)

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

InDegree of a vertex

A

Number of edges coming into the vertex

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

OutDegree of a vertex

A

Number of edges going out of the vertex

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

No of edges in a graph (HS theorem)

A

sum of degree of each vertex

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

terminal vertex(end vertex)

A

the vertex that the arrow is pointed too

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

Initial vertex

A

the vertex from which the arrow is pointed from

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

Complete Graph(Kn)

A

its a simple graph in which there is exactly one edge b/w each pair of distinct vertices in it

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

number of edges in kn

A

nC2 (n(n-1)/2)

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

Cycle (Cn)

A

It’s a path that starts from one vertex and ends at the same vertex

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

Wheel(Wn)

A

Obtained by adding a additional vertex to a cycle

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

Bipartite Graph

A

Its a graph in which the vertex set of v is partioned into 2 disjoint sets (v1 and v2) such that every edge in the graph connects a vertex in v1 and a vertex in v2 (making sure no edge in the graph connects to vertices of the same set aka v1 or v2).

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

Complete bipartite graph

A

its a bipartite graph in which each vertex in the set v1 connects to every vertex in the vertex set v2

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

Walk

A

its an alternating sequnce of vertices and connecting edges its the route from one vertex to another or from a vertex back to itself (vertices or edges can be repeated)

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

length of walk

A

number of edges in the walk

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

Trail

A

A walk that does not repeat any edges.

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

Path

A

A trail that does not repeat any vertices.

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

Cycle

A

A closed walk that does not repeat any edges.

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

Connected Graph

A

if there is a path b/w every pair of vertices in a graph

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

Disconnected

A

if there isnt a path b/w every pair of vertices in a graph

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

components

A

a disconnected graph consists of 2 or more connected graphs and each of these are called components

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

Regular Graph

A

If every vertex of a graph has the same degree then its called a regular graph

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

Subgraph

A

A graph H=(v1,e1) is called a subraph of G=(V,E) if v1 is a subset of V and e1 is a subset of E

32
Q

Spanning subgraph

A

A graph H is called a spanning subgraph if v1=V and e1 is a subset of E aka have all vertices

33
Q

Peterson Graph

A

graph with 10 vertices and 15 edges

34
Q

Isomorphism graphs

A

graphs having same number of vertices edges and edge connectivity are called isomorphic graphs

35
Q

disjoint subgraphs (edge/vertex)

A

2 subgraphs that have no (edges/ vertices) in common

36
Q

vertex/edge deleted subgraph

A

litrally a set of vertex/edges are removed from the og graph

37
Q

Adjacency matrix

A

a matrix which represents the adjacency of vertices in a graph

38
Q

incidence matrix

A

a matrix which represnts the incidence of edges on a vertex

39
Q

Euler Circuit

A

its a circuit that contains every edge of graph G

40
Q

Euler path

A

its a simple path in a graph containing every edge of G

41
Q

Hamiltonian circuit

A

Connected graph that is defined as a closed wal;k that traverse every vertice exactly once

42
Q

Binary relation

A

its the cartesian product of AXB and is called binary relation R of A to B

43
Q

semi in directed graphs

A

dont give a fuck about the arrows

44
Q

Tree

A

its a Connected Acyclic graph im which one vertex is identified as its root and the edges are called branches

45
Q

trvial

A

tree with a single vertex

46
Q

how many paths does a tree have

A

One (there must be no more than one path b/w any 2 vertices )

47
Q

Number of edges in a tree

A

number of vertices - 1

48
Q

Forest

A

undirected disconnected acyclic graph such that each component of it is a tree

49
Q

Null tree

A

a tree without edges is called a null tree

50
Q

bridge

A

an edge that when removed disconnects the graph

51
Q

Interior nodes

A

neither root or leaf nodes

52
Q

height of root node(tree)

A

length of the longest path from root to leaf node

53
Q

siblings(treee)

A

vertices with the same parent node

54
Q

Path length of a tree

A

defined as the sum of the path lengths of the pendant vertices from the root

55
Q

Distance (tree)

A

in a connected path the distance d(Vi ,Vj) between 2 vertics is the length of the shortest path

56
Q

Center(tree)

A

vertex with the lowest excentricity

57
Q

Eccentricity

A

its the farthest distance from a vertex to a pendant vertex in G

58
Q

bi center(tree)

A

2 center vertices

59
Q

m- ary tree

A

a rooted tree is called a m ary tree if every internal vertex has no more than m children

60
Q

Spanning Tree

A

in a simple graph G a spanning tree of G is a sub graph of G that is a tree consisting of every vertex of G

61
Q

Vertex connectivity

A

the min no of vertices to be removed such that the graph G gets disconnected

62
Q

vertex connectivity of any complete graph

A

no of componenets = n-1

63
Q

edge conectivity

A

min no of edges to be removed such that the graph G gets disconnected

64
Q

seprable graph

A

a graph is said to be separable if its vertex connectivity is 1

65
Q

fundamental cut set

A

if a edge in the cut set has a branch of a spanning tree in it then its called a fundamental cut set and rest are chords

66
Q

fundamental circuit

A

when a chord is added to a spanning tree T and then forming a exactly one circuit that circuit is called a fundamental circuit

67
Q

non separable

A

a graph that cant be disconnect by removing just one vertex

68
Q

face of a graph

A

its the rejoin formed by a cycle on parallel edges or loops in G its also the region denoted as f

69
Q

Jordan curve

A

non self intersecting continous closed curve in the planep

70
Q

planar graph

A

if it can be re drawn on a plane without crossovers such a drawing is called planar embedding of G

71
Q

embeddig of a graph

A

its the geometric representation of G drawn on a surface such that there is no crossovers

72
Q

spherical embedding

A

on a sphere

73
Q

Dual of a grtaph

A

The dual of a graph is a graph that is constructed by interchanging the roles of vertices and faces in the original graph. In other words, each vertex in the original graph becomes a face in the dual graph, and each face in the original graph becomes a vertex in the dual graph.

74
Q

self dual graphs

A

a graph is said to be self dual if its isomophic to its own dual

75
Q

properties of islolated matrix

A

each column hsa exactly 2 ones
no of ones in each row equals to the degree of the vertex
a row with 0s is for an isloated vertex
paralle edges provide identical columns

76
Q
A

Graph Theory (2 decks)

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