New Page 1
Welcome to basicsofcomputer.com

Home » Computer Dictionary » Letter G » Graph Definition/Meaning

# Graph Definition/Meaning:

A nonempty but finite set of vertices (or nodes) together with a set of edges that join pairs of distinct vertices. If an edge e joins vertices v1, and v2, then v1 and v2 are said to be incident with e and the vertices are said to be adjacent; e is the unordered pair (v1,v2).

A graph is usually depicted in a pictorial form in which the vertices appear as dots or other shapes, perhaps labeled for identification purposes, and the edges are shown as lines joining the appropriate points. If direction is added to each edge of a graph, a directed graph or digraph is obtained. The edges then form a finite set of ordered pairs of distinct vertices, and are often called arcs. In the pictorial representation, arrows can be placed on each edge. With no direction specified, the graph is said to be undirected. Although helpful visually these representations are not suitable for manipulation by computer. More useful representations use an incidence matrix or an adjacency matrix.

Graphs are used in a wide variety of ways in computing: the vertices will usually represent objects of some kind and the edges will represent connections of a physical or logical nature between the vertices. So graphs can be used to model in a mathematical fashion such diverse items as a computer and all its attached peripherals, a network of computers, parse trees, logical dependencies between subroutines or nonterminals in a grammar, VLSI diagrams, and related items in databases. Trees and lists are special kinds of graphs.

Certain variations exist in the definition of a graph. There is some dispute about whether one edge can join a vertex to itself, whether empty sets are involved, whether an infinite number of vertices and edges are permitted, and so on. See also connected graph.

## Near by Terms:

 Graceful Degradation Grammar Grandfather File, Grandfather Tape Granularity Graph Graphics Characters Gray Code Gray-Level Array Gray Scale Greatest Common Divisor (GCD) Greedy Method Greibach Normal Form Grosch's Law Group Group Code Group Code Recording (GCR) Group Graph Group Mark

New Page 1

Basic Computer Science

 » The Age of Information » Types of Computer and Digital Age » Input and Output Devices » Storage Devices Of Computer » Central Processing Unit » Software: The Power Behind The Power » Data Communication and Computer Networks » The Nature Of Information » The System Theory » Transaction Processing System (TPS) and Management Information System (MIS) » » Expert System (ES) and Office Information System (OIS)

Operating Systems

 » Introduction to Operating System » Introduction to Process Management » Threads and CPU Scheduling » Process Synchronization in Operating System » Deadlocks » Memory Management in Operating System » Virtual Memory in Operating System » File System Management in Operating System » I/O and Device Management » Security » Linux Operating System

Database Management System

 » Introduction to Database Systems » Database System Architecture » Database Administration and Database Development Process » The Entity-Relationship Model » Semantic Object Model » Logical Database Design and Relational Data Model » Normalization in Database » Transformation of E-R Model into Relational Data Model » Representing Semantic Object Model and Types of Semantic Object Model » Physical Database Design » Introduction to Structured Query Language (SQL) » Implementation of Relational Database and Database Application Design » Client Server Database Systems & Open Database Connectivity (ODBC)