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.2 Matrix Representation of Graphs

    Although a pictorial representation of a graph is very convenient for a visual study, other representations are better for computer processing. A matrix is a convenient and useful way of representing a graph to a computer. Matrices lend themselves easily to mechanical manipulations. Besides, many known results of matrix algebra can be readily applied to study the structural properties of graphs from an algebraic point of view. In many applications of graph theory, such as in electrical network analysis and operation research, matrices also turn out to be the natural way of expressing the problem.

    3.2.1 Incidence Matrix

    Let G be a graph with n vertices, e edges, and no self-loops. Define an n by e matrix A =[aij], whose n rows correspond to the n vertices and the e columns correspond to the e edges, as follows:

    The matrix element

    Aij = 1, if jth edge ej is incident on ith vertex vi, and

    = 0, otherwise.


    a b c d e f g h

    v1 0 0 0 1 0 1 0 0

    v2 0 0 0 0 1 1 1 1

    v3 0 0 0 0 0 0 0 1

    v4 1 1 1 0 1 0 0 0

    v5 0 0 1 1 0 0 1 0

    v6 1 1 0 0 0 0 0 0


    Fig. 3-4 Graph and its incidence matrix.

    Such a matrix A is called the vertex-edge incidence matrix, or simply incidence matrix. Matrix A for a graph G is sometimes also written as A(G). A graph and its incidence matrix are shown in Fig. 3-4. The incidence matrix contains only two elements, 0 and 1. Such a matrix is called a binary matrix or a (0, 1)-matrix.

    The following observations about the incidence matrix A can readily be made:

      1. Since every edge is incident on exactly two vertices, each column of A has exactly two 1s.
      2. The number of 1s in each row equals the degree of the corresponding vertex.
      3. A row with all 0s, therefore, represents an isolated vertex.
      4. Parallel edges in a graph produce identical columns in its incidence matrix, for example, columns 1 and 2 in Fig. 3-4.

    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