Scribd
Upload
45 views1 page

Graph: Characteristics

1. Graph theory studies interconnected objects represented as graphs consisting of vertices and edges. 2. A graph's characteristics include whether vertices are connected, if it allows self-loops or multiple edges between vertices, and if all vertices are reachable from each other. 3. Key elements are vertices, edges, paths between vertices, and the degree of edges meeting at each vertex.

Uploaded by

Ginny
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
45 views1 page

Graph: Characteristics

1. Graph theory studies interconnected objects represented as graphs consisting of vertices and edges. 2. A graph's characteristics include whether vertices are connected, if it allows self-loops or multiple edges between vertices, and if all vertices are reachable from each other. 3. Key elements are vertices, edges, paths between vertices, and the degree of edges meeting at each vertex.

Uploaded by

Ginny
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

GRAPH

Definitions:
1. GRAPH THEORY – Concerned with studying connections between objects. A
collection of objects which display interconnectedness is a graph.
2. GRAPH – Set of points and line segments or curves that connect these points.
CHARACTERISTICS
i. May contain vertices which are not connected to any vertex
ii. NULL EDGES are graphs with no edges at all
iii. Vertex can loop back to itself
iv. CONNECTED GRAPH are graphs where each vertex can be
reached from any other vertex by tracing a sequence of edges

3. VERTICES – Points in a graph


4. EDGES – Curves that connect them. Can be a straight line or a curve
5. EQUIVALENT GRAPHS – Graphs that form the same connections between
edges
6. PATH – Movement from one vertex to another by following an edges or
sequence of edges
7. DEGREE – The number of edges that meet at a vertex.
8. CLOSED PATH (circuit) – Path that ends at the same vertex where it started.
9. EULER PATH – Path through the graph that uses every edge only once
10. EULER CIRCUIT – Closed path that use the same edge twice, May cross a
vertex more than once
11. EULERIAN GRAPH THEOREM – Connected graph if and only if each vertex of
the graph has an even degree
12. FLEURY’S ALGORITHM – How to find the circuit
13. HAMILTONIAN CIRCUIT – Closed path that uses each vertex only once
14. WEIGHTED GRAPH – A graph in which each edge has a value or weight
15. PLANAR GRAPH – A graph which can be drawn in such a way that no edges
intersect each other except at the vertices (APPLICATION: circuit boards so that
a current can jump from one another and thus preventing the intersection of
currents.)
16. FACES – Regions enclosed by edges
17. INFINITE FACES – Surrounding the graph (*The relationship among vertices,
edges, and faces in a planar graph is described by a formula attributed to Euler.)
18. EULER’S FORMULA – v + f = e + 2, v – vertices, f – faces, e – edges

You might also like