Vertex Set

The vertex set of a graph refers to the collection of vertices or nodes in the graph. It is usually denoted V or V(G). The vertex set defines the entities being connected in the graph.

Some examples of vertex sets:

Cities in a transportation network
Computers in a network topology
Friends in a social network

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Graph {
  
  List<Vertex> vertices; // Vertex set

  public Graph(List<Vertex> vertices) {
    this.vertices = vertices;
  }

}

class Vertex {
  String name;

  Vertex(String name) {
    this.name = name;
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
struct Graph {
  
  vector<Vertex> vertices; // Vertex set

  Graph(vector<Vertex> vertices)
    : vertices(vertices) {}

};

struct Vertex {
  string name;

  Vertex(string name) : name(name) {}
};

Python example:

1
2
3
4
5
6
7
8
9
class Graph:

  def __init__(self, vertices):
    self.vertices = vertices

class Vertex:

  def __init__(self, name):
    self.name = name

The vertex set provides the entities and scope for relationships defined by edges in a graph. Important foundational component.

In graph theory, a vertex set is simply the set of all vertices (or nodes) in a graph. For instance, in a graph ( G ) with vertices ( A, B, C ), the vertex set is ( { A, B, C } ). The vertex set provides a way to define the graph structure along with the edge set.

Visualizing the concept can offer more clarity. Imagine three circles labeled as A, B, and C. These circles represent the vertices of a graph. When we talk about a vertex set, we mean a set that contains these labeled circles, or vertices.

    A ------ B
      \    /
       \  /
        C

Here, the vertex set can be represented as ( { A, B, C } ).

The vertex set encapsulates these vertices but doesn’t capture any relationships or connections between them—that part is done by the edge set.

So, when you see a vertex set, think of it as a collection of individual, isolated points that have the potential to be connected but aren’t necessarily connected yet.

Solution

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        // Create a vertex set
        Set<String> vertexSet = new HashSet<>();

        // Add vertices to the set
        vertexSet.add("A");
        vertexSet.add("B");
        vertexSet.add("C");

        // Display the vertex set
        System.out.println("Vertex Set: " + vertexSet);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    // Create a vertex set
    unordered_set<string> vertexSet;

    // Add vertices to the set
    vertexSet.insert("A");
    vertexSet.insert("B");
    vertexSet.insert("C");

    // Display the vertex set
    cout << "Vertex Set: ";
    for (const auto& vertex : vertexSet) {
        cout << vertex << " ";
    }
    cout << endl;

    return 0;
}

Python

1
2
3
4
5
# Create a vertex set
vertex_set = {"A", "B", "C"}

# Display the vertex set
print(f"Vertex Set: {vertex_set}")

Key Takeaway

The vertex set is a fundamental concept in graph theory. It’s one of the two main components that define a graph, the other being the edge set. Using programming languages like Java, C++, or Python, you can easily represent a vertex set with data structures like HashSets or dictionaries.