New Page 1
Welcome to basicsofcomputer.com

Home » Computer Dictionary » Letter C » Connected Graph Definition/Meaning

# Connected Graph Definition/Meaning:

A graph in which there is a path joining each pair of vertices, the graph being undirected. It is always possible to travel in a connected graph between one vertex and any other; no vertex is isolated. If a graph is not connected it will consist of several components, each of which is connected; such a graph is said to be disconnected.

If a graph G has e edges, v vertices, and p components, the rank of G, written p(G), is defined to be

v - p

The nullity of G, written u(G), is

e - v + p

Thus

p(G) + u(G) = e

With reference to a directed graph, a weakly connected graph is one in which the direction of each edge must be removed before the graph can be connected in the manner described above. If however there is a directed path between each pair of vertices u and v and another directed path from v back to u, the directed graph is strongly connected.

More formally, let G be a directed graph with vertices V and edges E. The set V can he partitioned into equivalence classes V1, V2..... under the relation that vertices u and v are equivalent iff there is a path from u to v and another from v to u. Let E1, E2.....be the sets of edges connecting vertices within V1, V2... Then each of the graphs G1, with vertices V1, and edges E1, is a strongly connected component of G. A strongly connected graph has precisely one strongly connected component.

The process of replacing each of the strongly connected components of a directed graph by a single vertex is known as condensation.

## Near by Terms:

COBOL or Cobol
Cocktail Shaker Sort
CODASVL
Code
8421Code
Codebook
Codec
Code Length
Coder-Decoder
Codeword, Codeword Length
Coding
Coding Bounds
Coding Standards
Coding Theorems
Coding Theory
Codomain
Collating Sequence
Collator
Collector
Collision, Collision Detection
Color Display
Colossus
Column-Major Order
Column-Ragged
Column Vector
COM
COMAL
Combinational Circuit (combinatorial circuit)
Combinatorial Circuit
Combinatorial
Combinatory Logic
Command
Command Control Program
Command Language
Comment
COMMON Area
Common Carrier
Communication Channel
Communication Network
Communication Processor
Communication Server
Communication Subnetwork (subnet)
Communication System
Communication Theory
Commutative Group (abelian group)
Commutative Law
Commutative Operation
Commutative Ring
Commutative Semiring
Compaction
Comparator
Comparison Counting Sort
Compartmentalization (compartmentation)
Compatibility
Compilation Time
Compiler
Compiler-Compiler
Complement Number System
Complete Graph
Complete Tree
Complexity
Complexity Classes
Complexity Function (work function)
Complexity Measure
Composition
Compression Coding
Computability
Computable (Turing computable)
Computable Function
Computational Psychology
Computer
Computer-Aidd Instruction (CAI)
Computer-Aided Manufacturing (CAM) CAM
Computer-Aided Testing (CAT)
Computer Architecture
Computer-Assisted Instruction (CAI)
Computer-Based Learning (CBL)
Computer Family
Computer Graphics
Computer Logic
Computer Mail
Computer-Managed Instruction (CMl)
Computer Manager
Computer Network
Computer Power
Computer Science
Computer- Services Manager
Computer Word
Concatenated Code
Concatenated Coding Systems
Concatenation
Concatenation Closure
Concentrator
Concurrency
Concurrent Programming
Conditional
Conditional Branch Instruction
Conditional Transfer
Condition Number
Confidence Interval
Configuration
Configuration Management
Configured -in. -off, -out
Confluent
Connected Graph
Connectedness
Connective
Connectivity of a Graph G
Connectivity Matrix
Consistency
Console
Constant
Construct
Consumable Resource
Contact Bounce
Context-Free Language (algebraic language)
Context-Sensitive Grammar
Context-Sensitive Language
Continuation
Continuous Signal System
Control Bus
Control Character
Control Circuitry
Control Cycle
Control Data Corporation
Control Design
Controlled Sharing
Controller
Control Line
Control Memory
Control Slack
Control Structure
Control Unit (CU)
Control Word
Convergence
Conversational Mode
Conversion
Convolution
Coprocessor
Copy
CORAL
Core Store
Coroutine
Corrective Maintenance
Correctness Proof
Correlation
COSMOS
Cost Function
Countable Set
Counter
Counting Problem
Coupled
Covariance
Covering

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)