Entry
Datastructure: Graph: Definition: What is a definition of a graph?
Jan 15th, 2005 11:42
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 15 January 2005 - 08:13 pm --------------------
Datastructure: Graph: Definition: What is a definition of a graph?
---
A graph is a structure of one or more points connected by lines.
e.g.
A B
o--------o
|
|
|
|
o----o
C D
---
Or more formal:
A graph is a set of points (called 'vertices' or 'nodes') connected by
lines (called 'edges').
---
Note:
A point represents here something, e.g. a city, a node in a
network, ...
The line connects these points (e.g. a road between cities, a network
cable between network nodes, ...)
e.g.
New York Los Angeles
o--------o
|
|
|
|
o----o
Miami Seattle
---
Note:
Direction:
A graph in which a direction is associated with the lines is called
a 'directed graph' or abbreviated 'digraph'.
e.g.
It might be that driving from city A to city B is different
from driving from city B to city A.
New York Los Angeles
o---->---o
|
|
|
|
o----o
Miami Seattle
---
Note:
Representation:
A graph may be represented by an adjacency matrix (e.g. using a
rectangular array with rows and columns) or a linked list (e.g. using
an array with a fixed amount of rows and a variable amount of columns).
---
Note:
Loops:
A graph with no loops in it is that graph in which there are no lines
joining a point with itself.
Or in other words there is only one path from that point to the other
point.
Figure: No loop (because only one line or path from A to B)
A B
o------o
Figure: Loop (because more than one line or path from A to B)
A B
o------o
| |
+------+
---
Note:
Tree:
A tree is a special case of a graph, that is a tree is a graph
without loops
---
Note:
Binary tree:
A binary tree is a special case of a tree.
Thus a binary tree is a special case of a graph.
---
---
Book: see also:
---
[book: Daintith, John / Nelson, R. David - the penguin dictionary of
mathematics - p. 150 'graph' - definition of a graph]
---
[book: Knuth, Donald Ervin - the Art of Computer Programming (volume
1 'Fundamental algorithms' / third edition) - ISBN: 0-201-89683-4 - p.
363]
---
[book: Sedgewick, Robert - algorithms - ISBN 0-201-06673-4 - p.
416 'Glossary']
---
[book: Wilson, Robert J. - introduction to graph theory - ISBN 0-582-
44397-0 - p. 1 'what is a graph']
---
---
Internet: see also:
---
Datastructure: Link: Overview: Can you give an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/32054/fid/1264
----------------------------------------------------------------------
