Posts
Graph: A set of nodes joined by arcs
Nodes: Points (vertices)
Arcs: Lines (edges)
Simple Graph: A graph without loops or multiple arcs
Subgraph of G: A graph whose nodes and arcs are all in the graph G
Complete Graph, Kn: A simple graph in which each of the nodes is connected by precisely one arc to every
Bipartite Graph: These graphs have two sets of nodes. The arcs only connect nodes from one set to the other, and do not connect nodes within a set
Complete Bipartite Graph: Every node in one set is connected to every node in the other set
Trail (Route): A sequence of arcs such that the end node of one arc is the start node of the next
Path: A trail with the restriction that no node is passed through more than once
Cycle: A closed trail where only the initial and final nodes are the same
Order of a Node: The number of arcs meeting at that node
Connected Graph: A graph where, for any two nodes, a path can be found connecting the two nodes
Eulerian Graph: A connected graph which has a closed trail containing every arc precisely once and all nodes
have even order
Semi-Eulerian Graph: A connected graph with a trail which is not closed that contains every arc precisely once and only 2 nodes have odd order
Non-Eulerian Graph
Planar Graph: A graph which can be drawn in a plane in such a way that arcs only meet at nodes
Euler’s Relationship: For any connected graph drawn in the plane with R regions, N nodes and A arcs, R + N = A + 2
Network (Weighted Graph): A graph whose arcs have weights (numbers)
Digraph (Directed Graph): A graph with directed arcs
Matrix: A table showing all the information about the weights in a network
Tree: A connected graph with no cycles
Spanning Tree: Subgraphs that are also trees
Minimum Spanning Tree: A spanning tree where the total weight of the arcs is as small as possible
©2011 Grant Dwyer
No comments:
Post a Comment