Module 1

Question 1

Graph

Answer 1

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

Question 2

Trvial Graph

Answer 2

graph with a single vertex

Question 3

Null(empty Graph)

Answer 3

No edges

Question 4

Isolated Vertex

Answer 4

a Vertex that is not adjacent to any other vertex

Question 5

Parallel edge

Answer 5

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

Question 6

Order and Size

Answer 6

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

Question 7

Simple Graph

Answer 7

Graph with no self loops or parallel edges

Question 8

Incidence on graph

Answer 8

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

Question 9

adjacent vertex

Answer 9

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

Question 10

degree of a vertex

Answer 10

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

Question 11

InDegree of a vertex

Answer 11

Number of edges coming into the vertex

Question 12

OutDegree of a vertex

Answer 12

Number of edges going out of the vertex

Question 13

No of edges in a graph (HS theorem)

Answer 13

sum of degree of each vertex

Question 14

terminal vertex(end vertex)

Answer 14

the vertex that the arrow is pointed too

Question 15

Initial vertex

Answer 15

the vertex from which the arrow is pointed from

Question 16

Complete Graph(Kn)

Answer 16

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

Question 17

number of edges in kn

Answer 17

nC2 (n(n-1)/2)

Question 18

Cycle (Cn)

Answer 18

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

Question 19

Wheel(Wn)

Answer 19

Obtained by adding a additional vertex to a cycle

Question 20

Bipartite Graph

Answer 20

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).

Question 21

Complete bipartite graph

Answer 21

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

Question 22

Walk

Answer 22

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)

Question 23

length of walk

Answer 23

number of edges in the walk

Question 24

Trail

Answer 24

A walk that does not repeat any edges.

Question 25

Path

Answer 25

A trail that does not repeat any vertices.

Question 26

Cycle

Answer 26

A closed walk that does not repeat any edges.

Question 27

Connected Graph

Answer 27

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

Question 28

Disconnected

Answer 28

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

Question 29

components

Answer 29

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

Question 30

Regular Graph

Answer 30

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

Question 31

Subgraph

Answer 31

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

Question 32

Spanning subgraph

Answer 32

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

Question 33

Peterson Graph

Answer 33

graph with 10 vertices and 15 edges

Question 34

Isomorphism graphs

Answer 34

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

Question 35

disjoint subgraphs (edge/vertex)

Answer 35

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

Question 36

vertex/edge deleted subgraph

Answer 36

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

Question 37

Adjacency matrix

Answer 37

a matrix which represents the adjacency of vertices in a graph

Question 38

incidence matrix

Answer 38

a matrix which represnts the incidence of edges on a vertex

Question 39

Euler Circuit

Answer 39

its a circuit that contains every edge of graph G

Question 40

Euler path

Answer 40

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

Question 41

Hamiltonian circuit

Answer 41

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

Question 42

Binary relation

Answer 42

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

Question 43

semi in directed graphs

Answer 43

dont give a fuck about the arrows

Question 44

Tree

Answer 44

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

Question 45

trvial

Answer 45

tree with a single vertex

Question 46

how many paths does a tree have

Answer 46

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

Question 47

Number of edges in a tree

Answer 47

number of vertices - 1

Question 48

Forest

Answer 48

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

Question 49

Null tree

Answer 49

a tree without edges is called a null tree

Question 50

bridge

Answer 50

an edge that when removed disconnects the graph

Question 51

Interior nodes

Answer 51

neither root or leaf nodes

Question 52

height of root node(tree)

Answer 52

length of the longest path from root to leaf node

Question 53

siblings(treee)

Answer 53

vertices with the same parent node

Question 54

Path length of a tree

Answer 54

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

Question 55

Distance (tree)

Answer 55

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

Question 56

Center(tree)

Answer 56

vertex with the lowest excentricity

Question 57

Eccentricity

Answer 57

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

Question 58

bi center(tree)

Answer 58

2 center vertices

Question 59

m- ary tree

Answer 59

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

Question 60

Spanning Tree

Answer 60

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

Question 61

Vertex connectivity

Answer 61

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

Question 62

vertex connectivity of any complete graph

Answer 62

no of componenets = n-1

Question 63

edge conectivity

Answer 63

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

Question 64

seprable graph

Answer 64

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

Question 65

fundamental cut set

Answer 65

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

Question 66

fundamental circuit

Answer 66

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

Question 67

non separable

Answer 67

a graph that cant be disconnect by removing just one vertex

Question 68

face of a graph

Answer 68

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

Question 69

Jordan curve

Answer 69

non self intersecting continous closed curve in the planep

Question 70

planar graph

Answer 70

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

Question 71

embeddig of a graph

Answer 71

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

Question 72

spherical embedding

Answer 72

on a sphere

Question 73

Dual of a grtaph

Answer 73

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.

Question 74

self dual graphs

Answer 74

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

Question 75

properties of islolated matrix

Answer 75

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