Intro Graph Theory: Components Connectivity

Click For Summary
SUMMARY

This discussion centers on the definitions of components and connectivity in graph theory. A component consists of vertices connected by a path, and a graph is considered connected if it contains only one component. The user seeks clarification on the nature of paths, specifically regarding the repetition of vertices. The provided link offers additional definitions relevant to graph theory.

PREREQUISITES
  • Understanding of basic graph theory concepts, including vertices and edges.
  • Familiarity with the definition of subgraphs.
  • Knowledge of paths in graph theory.
  • Basic comprehension of connected and disconnected graphs.
NEXT STEPS
  • Research the concept of "connected components" in graph theory.
  • Explore the properties of "Eulerian paths" and "Hamiltonian paths".
  • Learn about "graph traversal algorithms" such as Depth-First Search (DFS) and Breadth-First Search (BFS).
  • Investigate the "applications of graph theory" in real-world scenarios.
USEFUL FOR

Students, educators, and professionals in mathematics, computer science, and data analysis who are looking to deepen their understanding of graph theory concepts, particularly components and connectivity.

wubie
Hello,

I am having trouble understanding the definition of components and connectivity. Here is the definition I have been given in my text:


Two vertices of a graph that are joined by a path are said to belong to the same component of the graph. If the whole graph is one component, then it is said to be connected. Thus the components are connected subgraphs which are not contained in larger connected subgraphs.

Alright, I know that a subgraph is a subset of vertices and edges which itself forms a graph. I also know that a path is a subgraph in which no edge or vertex is repeated except for perhaps the first and last vertex.


Could someone perhaps reword the above definition of components and connectivity or provide a better definition of components and connectivity for me please? Thankyou.

I also have another question regarding paths. I know that perhaps the first and last vertex may be repeated, but does that mean that a subgraph is still a path if both the last and first vertex are repeated? Or that if a subgraph is still a path if either the first or last vertex is repeated? Or can both situations occur?
 
Last edited by a moderator:
Mathematics news on Phys.org

Similar threads

Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
7K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
4K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Interesting graph theory problem
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Find Two Equal Length Paths in a Tree Graph
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Why is Graham's number a factor of 3?
  • · Replies 12 ·
Replies
12
Views
5K
Prove the decomposition of a graph w/ even edges produce a 2-path set
  • · Replies 1 ·
Replies
1
Views
2K