✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-096

Vertices, Edges, Degree, and Adjacency

Vertices, edges, degree, and adjacency are fundamental graph theory concepts. They describe the objects in a graph, the connections between them, the number of incident edges, and the relationships between neighboring vertices.

Explanation

Overview

Vertices, Edges, Degree, and Adjacency describes a computational idea or method used to address a defined class of problems. In practical use, it should be understood through its requirements, behavior, and the outcomes described here: Vertices, edges, degree, and adjacency are fundamental graph theory concepts. They describe the objects in a graph, the connections between them, the number of incident edges, and the relationships between neighboring vertices.

Applications

Counting friendships in social networks; Analyzing connections in computer networks; Modeling road intersections; Studying communication relationships; Identifying highly connected entities

Limitations

The suitability of vertices, edges, degree, and adjacency depends on the exact problem requirements and the assumptions made about the input.; An implementation of vertices, edges, degree, and adjacency can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For vertices, edges, degree, and adjacency, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Related concepts

Graph Theory; Directed and Undirected Graphs; Graph Connectivity; Adjacency Matrix; Adjacency List

Example or application

A worked example has not yet been added.

Vertices

Definition

A vertex is an individual node or entity in a graph.

Alternative Name

Node

Example

In a social network, each user can be represented as a vertex.

Notation

A vertex is commonly represented by a letter such as A, B, or C.

Edges

Definition

An edge is a connection between two vertices.

Undirected Notation

{u, v}

Directed Notation

(u, v)

Example

An edge between A and B represents a relationship or connection between those vertices.

Degree

Definition

The degree of a vertex in an undirected graph is the number of edges incident to that vertex.

Notation

deg(v)

Example

If vertex A is connected to B, C, and D, then deg(A) = 3.

Self Loop Rule

A self-loop contributes two to the degree of a vertex in an undirected graph.

Handshaking Lemma

The sum of the degrees of all vertices in an undirected graph equals twice the number of edges.

Handshaking Formula

Σ deg(v) = 2|E|

Directed Degree

Indegree

The number of directed edges entering a vertex.

Outdegree

The number of directed edges leaving a vertex.

Notation

Indegree

deg⁻(v)

Outdegree

deg⁺(v)

Relationship

The sum of all indegrees equals the sum of all outdegrees, and both equal the number of directed edges.

Adjacency

Definition

Two vertices are adjacent when an edge directly connects them.

Neighbor

A neighboring vertex is a vertex directly connected to another vertex.

Undirected Adjacency

Adjacency is symmetric: if A is adjacent to B, then B is adjacent to A.

Directed Adjacency

Adjacency follows the direction of the edge.

Incidence

An edge is incident to the vertices that it connects.

Path

A path is a sequence of vertices in which consecutive vertices are connected by edges.

Walk

A walk is a sequence of vertices and edges in which vertices or edges may be repeated.

Trail

A trail is a walk that does not repeat edges.

Simple Path

A simple path does not repeat vertices.

Isolated Vertex

A vertex with degree zero and no incident edges.

Pendant Vertex

A vertex with degree one in an undirected graph.

Example Graph

Vertices

  • A

  • B

  • C

  • D

Edges

    • A

    • B

    • A

    • C

    • B

    • C

    • C

    • D

Degrees

A

2

B

2

C

3

D

1

Important Properties

  • Every edge in an undirected graph contributes two to the total degree count.

  • An undirected edge connects two vertices without specifying a direction.

  • A directed edge has a source and a destination.

  • An isolated vertex has no adjacent vertices.

  • A vertex may have several neighbors or none.

Applications

  • Counting friendships in social networks

  • Analyzing connections in computer networks

  • Modeling road intersections

  • Studying communication relationships

  • Identifying highly connected entities

Related Concepts

  • Graph Theory

  • Directed and Undirected Graphs

  • Graph Connectivity

  • Adjacency Matrix

  • Adjacency List

Definition

Vertices, Edges, Degree, and Adjacency describes a computational idea or method used to address a defined class of problems. In practical use, it should be understood through its requirements, behavior, and the outcomes described here: Vertices, edges, degree, and adjacency are fundamental graph theory concepts. They describe the objects in a graph, the connections between them, the number of incident edges, and the relationships between neighboring vertices.

Limitations

  • The suitability of vertices, edges, degree, and adjacency depends on the exact problem requirements and the assumptions made about the input.

  • An implementation of vertices, edges, degree, and adjacency can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.

  • For vertices, edges, degree, and adjacency, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Practice Questions

QuestionAnswer

What is the main purpose of vertices, edges, degree, and adjacency?

Vertices, edges, degree, and adjacency are fundamental graph theory concepts. They describe the objects in a graph, the connections between them, the number of incident edges, and the relationships between neighboring vertices.

What should be checked before applying vertices, edges, degree, and adjacency?

For vertices, edges, degree, and adjacency, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of vertices, edges, degree, and adjacency be validated?

Trace a representative vertices, edges, degree, and adjacency case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of vertices, edges, degree, and adjacency.

  • Identify the assumptions, inputs, and conditions relevant to vertices, edges, degree, and adjacency.

  • Evaluate an application of vertices, edges, degree, and adjacency for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures