|
Question 478460: The problems says:
Given the graph, Name an edge that is a bridge, if any.
I hope someone can help me!
See the actual graph here:
http://www.flickr.com/photos/62474130@N03/6013438765/
Answer by Theo(13342)   (Show Source):
You can put this solution on YOUR website! here's a reference from graph theory
http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/connectivity.htm
you have all these points that are connected by lines.
a connection is defined as a set of points connected by lines.
a bridge is a line that connects sets of points.
if you remove the bridge, the number of sets of points increases.
these sets of points are called connections.
in your diagram (shown below), the line BC would be a bridge because it's removal creates 2 connected sets of points.
those 2 sets of connected points would be:
DFE
CAB
the line FE would not be a bridge because it's removal would not create an addition set of points because points F and E are still connected to the graph through lines FD and ED.
your flicker photo
here's another reference that's not quite as easy to follow but does contain references to all the terms that you supplied in your question.
http://www.enotes.com/topic/Bridge_%28graph_theory%29
here's a dictionary of terms used in bridge theory
http://en.wiktionary.org/wiki/Appendix:Glossary_of_graph_theory
bridge theory is used in telecommunications networks like the internet. if a node (server, bridge, router) is connected to the network through only one path (the line would be the path), then cutting that path isolates the node. 2 or more connected paths between that node and the rest of the network increases its survivability.
there's lots more references out there.
just go to google or yahoo or any other search engine and do a search on "graph theory".
the answer to your question is that the line DC (also called an edge) is a bridge because its removal creates 2 isolated sets of points, otherwise known as connections (i believe - check the references for the exact definition).
|
|
|
| |
