Component (graph theory) has been listed as one of the
Mathematics good articles under the
good article criteria. If you can improve it further,
please do so. If it no longer meets these criteria, you can
reassess it. Review: March 5, 2022. ( Reviewed version). |
This is the
talk page for discussing improvements to the
Component (graph theory) article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This
level-5 vital article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
User:DPoon has suggested that strongly connected component be merged here. I strongly disagree. We could perhaps use an article that would survey various notions of components in graph theory (connected components and biconnected components of undirected graphs, strongly connected components of directed graphs, etc) but both connected components and strongly connected components deserve their own articles: they are fundamental, important, have plenty of algorithmic depth, etc. And while connected components are reasonably intuitive and natural, strongly connected components require more care to define and use; including that material here would necessarily make it shorter and harder to understand while also confusing readers who only care about the undirected case. — David Eppstein ( talk) 20:01, 1 October 2008 (UTC)
This article is definitely not a stub so I have upgraded it to start. I am not sure if it meets the criteria for C-class so left it at that. Acb314 ( talk) 11:38, 14 August 2009 (UTC)
According to this articles definition:
I'm looking for the name you can give to a "connected component" of a directed graph. That is, I'm looking for XYZ, for which the following definition holds:
It should be called something like "maximally connected subgraph of a directed graph", though I guess there is already a special name for it. Thanks, -- Abdull ( talk) 21:50, 2 August 2010 (UTC)
The Algorithms section talks about amortized O(|V|) deletion of edges in disjoint-set data structure. Amortized constant time per edge delete can be achieved in disjoint-set while still maintaning the same time complexity of the other operations. Construction of such a data structure is described in several papers, that can be easily found using "union find delete" query in any search engine (Google being probably the best one). I am not familiar with Wikipedia's policies and I don't feel confident to change this article as I am just an undergrad student of computer science. 78.128.196.3 ( talk) 09:05, 27 April 2013 (UTC)
A component, by definition is a connected subgraph of a graph, the term connected component is redundant, and does not appear in most texts.
The term "connected component" does however appear a lot in computer science literature, from what I've seen online. However, this is more of a math article than it is a compsci one, so I would argue the definition and use of the term seen most in Graph Theory texts would be more suitable. — Preceding unsigned comment added by Zer0dept ( talk • contribs) 22:16, 17 March 2019 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Ovinus ( talk · contribs) 23:19, 28 February 2022 (UTC)
Hi, I'll take this one up. A cursory look through the article reveals it's in good shape. For reference, I know graph theory concepts that would be found in a typical undergrad computer science sequence. Any edits I make to the article will be minor (and not something I'll be a stickler on). Ovinus ( talk) 23:19, 28 February 2022 (UTC)
constructed in linear timeI'd specify "linear time in the number of vertices" to ensure it's not confused as linear in component count. ("sublinear time algorithms ... " later is clear)
low time per changeWould "constant time", "roughly constant time" or "amortized constant time" be too technical here?
For instance, the graph shown in the first illustration has three components.I'd be a bit more explicit that the components are disjoint, or we're just stating something obvious; also, "three components" is stated in the caption. Maybe something like "For instance, the three components of the graph in the first illustration are disjoint, and together constitute the whole graph."
as sets of vertices, the equivalence classes of vertices,The second part can be removed as the meaning is clear
for more advanced forms of graph connectivityI'd just say "for other forms"; advancedness is subjective
topological connected componentsI'd say "topologically", but this is minor and perhaps slightly imprecise
and representing its edges as line segments between those pointsI wouldn't call this a "representation" per se, since information about vertices of degree two are lost in the topological setting. Maybe "considering"?
and in topological graph theory it can be interpreted as the zeroth Betti number of the graphThis seems a bit redundant, since a construction was just essentially given (so it's just terminology)
Mostly prose nitpicks here:
To find all the components of a graph, loop through its verticesThe imperative mood feels a bit off here; maybe just "Finding all the components of a graph is/can be done by looping ... "
breadth first or depth firsthyphenate
Hopcroft & Tarjan (1973) describe ... "well known"What is the utility of this vs. a plain citation? If the main thrust is "well known" then I think "essentially this algorithm" can be removed
or as likely to be part of objects depicted in the imagerm "depicted in the image"
Researchers in this arearm "in this area"
and labeling them as objectsThis seems quite clear; removing it would make the sentence more concise
allowing it to be processed in pixel orderProvide why this is important (I assume it's to do with cache locality?)
I totally overestimated my knowledge in this area; if you felt my review wasn't thorough let me know. Ovinus ( talk) 00:32, 1 March 2022 (UTC)
@ Ovinus: I think I've responded to everything above, so please take another look. — David Eppstein ( talk) 17:51, 2 March 2022 (UTC)
allows them to be subjected to additional processing-> "allows additional processing", since you immediately describe the processing afterward and it's clear that it's on the identified components. I'll promote after these are addressed. Ovinus ( talk) 18:35, 2 March 2022 (UTC)
Component (graph theory) has been listed as one of the
Mathematics good articles under the
good article criteria. If you can improve it further,
please do so. If it no longer meets these criteria, you can
reassess it. Review: March 5, 2022. ( Reviewed version). |
This is the
talk page for discussing improvements to the
Component (graph theory) article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This
level-5 vital article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
User:DPoon has suggested that strongly connected component be merged here. I strongly disagree. We could perhaps use an article that would survey various notions of components in graph theory (connected components and biconnected components of undirected graphs, strongly connected components of directed graphs, etc) but both connected components and strongly connected components deserve their own articles: they are fundamental, important, have plenty of algorithmic depth, etc. And while connected components are reasonably intuitive and natural, strongly connected components require more care to define and use; including that material here would necessarily make it shorter and harder to understand while also confusing readers who only care about the undirected case. — David Eppstein ( talk) 20:01, 1 October 2008 (UTC)
This article is definitely not a stub so I have upgraded it to start. I am not sure if it meets the criteria for C-class so left it at that. Acb314 ( talk) 11:38, 14 August 2009 (UTC)
According to this articles definition:
I'm looking for the name you can give to a "connected component" of a directed graph. That is, I'm looking for XYZ, for which the following definition holds:
It should be called something like "maximally connected subgraph of a directed graph", though I guess there is already a special name for it. Thanks, -- Abdull ( talk) 21:50, 2 August 2010 (UTC)
The Algorithms section talks about amortized O(|V|) deletion of edges in disjoint-set data structure. Amortized constant time per edge delete can be achieved in disjoint-set while still maintaning the same time complexity of the other operations. Construction of such a data structure is described in several papers, that can be easily found using "union find delete" query in any search engine (Google being probably the best one). I am not familiar with Wikipedia's policies and I don't feel confident to change this article as I am just an undergrad student of computer science. 78.128.196.3 ( talk) 09:05, 27 April 2013 (UTC)
A component, by definition is a connected subgraph of a graph, the term connected component is redundant, and does not appear in most texts.
The term "connected component" does however appear a lot in computer science literature, from what I've seen online. However, this is more of a math article than it is a compsci one, so I would argue the definition and use of the term seen most in Graph Theory texts would be more suitable. — Preceding unsigned comment added by Zer0dept ( talk • contribs) 22:16, 17 March 2019 (UTC)
GA toolbox |
---|
Reviewing |
Reviewer: Ovinus ( talk · contribs) 23:19, 28 February 2022 (UTC)
Hi, I'll take this one up. A cursory look through the article reveals it's in good shape. For reference, I know graph theory concepts that would be found in a typical undergrad computer science sequence. Any edits I make to the article will be minor (and not something I'll be a stickler on). Ovinus ( talk) 23:19, 28 February 2022 (UTC)
constructed in linear timeI'd specify "linear time in the number of vertices" to ensure it's not confused as linear in component count. ("sublinear time algorithms ... " later is clear)
low time per changeWould "constant time", "roughly constant time" or "amortized constant time" be too technical here?
For instance, the graph shown in the first illustration has three components.I'd be a bit more explicit that the components are disjoint, or we're just stating something obvious; also, "three components" is stated in the caption. Maybe something like "For instance, the three components of the graph in the first illustration are disjoint, and together constitute the whole graph."
as sets of vertices, the equivalence classes of vertices,The second part can be removed as the meaning is clear
for more advanced forms of graph connectivityI'd just say "for other forms"; advancedness is subjective
topological connected componentsI'd say "topologically", but this is minor and perhaps slightly imprecise
and representing its edges as line segments between those pointsI wouldn't call this a "representation" per se, since information about vertices of degree two are lost in the topological setting. Maybe "considering"?
and in topological graph theory it can be interpreted as the zeroth Betti number of the graphThis seems a bit redundant, since a construction was just essentially given (so it's just terminology)
Mostly prose nitpicks here:
To find all the components of a graph, loop through its verticesThe imperative mood feels a bit off here; maybe just "Finding all the components of a graph is/can be done by looping ... "
breadth first or depth firsthyphenate
Hopcroft & Tarjan (1973) describe ... "well known"What is the utility of this vs. a plain citation? If the main thrust is "well known" then I think "essentially this algorithm" can be removed
or as likely to be part of objects depicted in the imagerm "depicted in the image"
Researchers in this arearm "in this area"
and labeling them as objectsThis seems quite clear; removing it would make the sentence more concise
allowing it to be processed in pixel orderProvide why this is important (I assume it's to do with cache locality?)
I totally overestimated my knowledge in this area; if you felt my review wasn't thorough let me know. Ovinus ( talk) 00:32, 1 March 2022 (UTC)
@ Ovinus: I think I've responded to everything above, so please take another look. — David Eppstein ( talk) 17:51, 2 March 2022 (UTC)
allows them to be subjected to additional processing-> "allows additional processing", since you immediately describe the processing afterward and it's clear that it's on the identified components. I'll promote after these are addressed. Ovinus ( talk) 18:35, 2 March 2022 (UTC)