• DR RAJNI

We have proposed studying properties that “almost always” hold. This phrase has meaning in the context of a probability model. Definition. Given a sequence of probability spaces, let q_n be the probability that property Q holds in the nth space. Property Q almost always holds if lim┬(n→∞)⁡〖q_n 〗=1. For us, the nth space is a probability distribution over n‐vertex graphs. When property Q almost always holds, we say almost every graph has property Q Making aU graphs with vertex set [n] equally likely is equivalent to letting each vertex pair appear as an edge with probability 1/2. Models where edges arise independently with the same probability are the most common for random graphs because they lead to the simplest computations. We allow this probability to depend on n. Definition. Model A Given n and p=p(n) , generate graphs with vertex set [n] by letting each pair be an edge with probability p, independently. Each graph with m edges has probability p^m (1-p) (_2^n) -m. The random variable G^p denotes a graph drawn from this probability space. “The random graph” means Model A with p=1/2, which makes all graphs with vertex set [n] equally likely. Computations are much simpler for graphs with a fixed vertex set (''labeled^'' graphs) than for random isomorphism classes. Since inputs to algorithms are graphs with specified vertex sets, this model is consistent with applications. We often measure running times of algorithms in terms of the number of vertices and number of edges; hence we may want to control the number of edges. This suggests a model in which the n‐vertex labeled graphs with m edges are equally likely. (We use m to count edgesin this section because the number e=2.71828… plays an important role in asymptotic arguments.) Definition. Model B: Given n and m=m(n) , let each graph with vertex set [n] and m edges occur with probability (■(N@m))^(-1) , where N=(■(n@2)). The random vańable G^m denotes a graph generated in this way.

partition , probability , standard deviation , threshold , composition, binomial distribution.

"PROPERTIES OF GRAPHS IN GRAPH THEORY", International Journal of Emerging Technologies and Innovative Research (www.jetir.org), ISSN:2349-5162, Vol.7, Issue 1, page no.679-683, January-2020, Available :http://www.jetir.org/papers/JETIR2001089.pdf

"PROPERTIES OF GRAPHS IN GRAPH THEORY", International Journal of Emerging Technologies and Innovative Research (www.jetir.org | UGC and issn Approved), ISSN:2349-5162, Vol.7, Issue 1, page no. pp679-683, January-2020, Available at : http://www.jetir.org/papers/JETIR2001089.pdf