Vyom World.com  . Let's Touch the Sky Together!  
. . . . . . .
VyomWorld.com Home
Free Magazines!
VyomLinks.com Home
JobsAssist.com Home
Vyom Network
Contact Us
 Jobs & Careers
Resume Submitter
Placement Papers
IT Companies Directory
Computer Jobs
Interview Questions
Online Exams
Vyom Career eMag.
Screensavers New!
SMS Jokes
 Source Codes Library
Source Codes Home
ASP Source Codes
C Source Codes
C++ Source Codes
COBOL Source Codes
Java Source Codes
Pascal Source Codes
Submit Source Codes
GATE an Overview
GATE Preparation
Study Materal
GRE an Overview
GRE Questions
GRE Preparation
GRE Universities
 TOEFL Preparation
TOEFL Resources
 GMAT Preparation
GMAT Resources
 MBA Preparation
MBA Resources
 Networking Concepts
Networking Concepts
 Testing Preparation
Testing Resources
Free Traffic Builder
Webmaster Articles
Web Hosting
Hardware Tutorial
1500 Free eBooks New!
 FREE Publications
Vyom Career eMag.
Get 9,000+ Interview Questions & Answers in an eBook.

  • 9,000+ Interview Questions
  • All Questions Answered
  • 5 FREE Bonuses
  • Free Upgrades

    Get it now!

    Post your Resume to 5800+ Companies

    Reliable Web Hosting

    Get 9,000+ Interview Questions with Answers in an eBook


    Analysis and Design of Algorithms


    3.1 Introduction to Graph Theory

    3.1.1 What is graph?

    A graph G = (V, E) consists of a set of objects V = {v1, v2, } called vertices, and another set E = {e1, e2, } whose elements are called edges. Each edge ek in E is identified with an unordered pair (vi, vj) of vertices. The vertices vi, vj associated with edge ek are called the end vertices of ek. The most common representation of graph is by means of a diagram, in which the vertices are represented as points and each edge as a line segment joining its end vertices. Often this diagram itself is referred to as a graph.

    Fig 3-1.

    In the Fig. 3-1 edge e1 having same vertex as both its end vertices is called a self-loop. There may be more than one edge associated with a given pair of vertices, for example e4 and e5 in Fig. 3-1. Such edges are referred to as parallel edges.

    A graph that has neither self-loop nor parallel edges are called a simple graph, otherwise it is called general graph. It should also be noted that, in drawing a graph, it is immaterial whether the lines are drawn straight or curved, long or short: what is important is the incidence between the edges and vertices.

    A graph is also called a linear complex, a 1-complex, or a one-dimensional complex. A vertex is also referred to as a node, a junction, a point, 0-cell, or an 0-simplex. Other terms used for an edge are a branch, a line, an element, a 1-cell, an arc, and a 1-simplex.

    Because of its inherent simplicity, graph theory has a very wide range of applications in engineering, physical, social, and biological sciences, linguistics, and in numerous other areas. A graph can be used to represent almost any physical situation involving discrete objects and a relationship among them.


    3.1.2 Finite and Infinite Graphs

    Although in the definition of a graph neither the vertex set V nor the edge set E need be finite, in most of the theory and almost all applications these sets are finite. A graph with a finite number of vertices as well as a finite number of edges is called a finite graph; otherwise, it is an infinite graph.

    3.1.3 Incidence and Degree

    When a vertex vi is an end vertex of some edge ej, vi and ej are said to be incident with (on or to) each other. In Fig. 3-1, for example, edges e2, e6, and e7 are incident with vertex v4. Two nonparallel edges are said to be adjacent if they are incident on a common vertex. For example, e2 and e7 in Fig. 3-1 are adjacent. Similarly, two vertices are said to be adjacent if they are the end vertices of the same edge. In Fig. 3-1, v4 and v5 are adjacent, but v1 and v4 are not.

    The number of edges incident on a vertex vi, with self-loops counted twice is called the degree, d(vi), of vertex vi. In Fig. 3-1, for example, d(v1) = d(v3) = d(v4) = 3, d(v2) = 4, and d(v5) = 1. The degree of a vertex is sometimes also referred to as its valency. Since each edge contributes two degrees, the sum of the degrees of all vertices in G is twice the number of edges in G.

    3.1.4 Isolated vertex, Pendent vertex, and Null graph

    A vertex having no incident edge is called an isolated vertex. In other words, isolated vertices are vertices with zero degree. Vertex v4 and v7 in Fig. 3-2, for example, are isolated vertices. A vertex of degree one is called a pendent vertex or an end vertex. Vertex v3 in Fig. 3-2 is a pendant vertex. Two adjacent edges are said to be in series if their common vertex is of degree two. In Fig. 3-2, the two edges incident on v1 are in series.


    Fig. 3-2 Graph containing isolated vertices, series edges and a pendant vertex.

    In the definition of a graph G = (V, E), it is possible for the edge set E to be empty. Such a graph, without any edges, is called a null graph. In other words, every vertex in a null graph is an isolated vertex. A null graph of six vertices is shown in Fig. 3-3. Although the edge set E may be empty, the vertex set V must not be empty; otherwise, there is no graph. In other words, by definition, a graph must have at least one vertex.


    Fig. 3-3 Null graph of six vertices.

    Study Notes Home | Next Section>>


    Discussion Center



    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    Recently Updated: New Placement Papers added.
    Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory

    Copyright ©2003-2019 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy