Mapa mental
Graphs & Networks

Conteúdo do mapa
Graphs & Networks
Deffinitions
- A graph is a finite number of points (vertices or nodes) joined by a line (edges or arcs).
- An edges has a vertex at each end. An edge with the same vertex at each end is called a loop.
- The degree or order (or valency) of a vertex is the number of edges joining it.
- A walk is a sequence of edges in which the edges is the beginning of the next (cant go back on yourself).
- A trail is a walk where no edge is repeated (vertices can be crossed more than once). All trails are walks.
- Eulerian trail: visits ever edge in the graph exactly one.
- A path is a trail in which each vertex is traversed only once.
- Hamiltonian path: visits every vertex in the graph exactly once.
- A network is a graph where the edges have associated numbers with them. These are called their weights and usually represent distance.
Types of graphs
- Connected graph: Where there exists a path between ever pair of vertices (directly or via other vertices).
- Planar graph: no arcs cross.
- Isomorphic graph: graphs which have exactly the same properties (nodes, arc, order of nodes the same.
- Simple connected graph: a connected graph that has no loops and no more than one edge connect to any pair of vertices.
- Digraph: where at least one edge has a direction.
- Complete graph: a simple connected graph where every possible pair of vertices is connected.
- To calculate the number of edges use the formula n(n-1) all divided by 2. Where n is the number of nodes.
- Bipartite graph: where the nodes are split into two distinct sets. The set can be connected by arcs but the nodes within a set cannot connect.
- Calculate number of edges in a complete Bipartite graph. Time the number of nodes on one set by the number of nodes on the other set.
- Tree: is a connected graph with no cycles.
- Spanning tree: sub graph that includes all the vertices of the graph and is also a tree.
- Complement graph: two sub graphs of a graph that have the arcs the other sub-graph doesn't.
Alternate ways of representing graphs.
- In a table called an Incidence or adjacency matrix where the columns and rows represent the vertices and the cells show the number of edges joining the pairs of vertices.
- A digraph can be represented in a similar way but there must be a direction.
Alternate way of representing a Network.
- Using a distance matrix similar to a incidence matrix but instead of the cells representing the vertices they represent the weights.
- In a minimum spanning tree or minimum connector which is the smallest total weight of the edges possible.
Minimum connector algorithms
- Kruskals: Select the shortest edge, Select the next shortest edge that doesn't create a cycle, Repeat till all vertices are connected and there are no cycles. Whilst doing this note down the order and weight at the side and then calculate your total weight.
- Prims: Select any vertex (unless specified), select the shortest edge connected to that vertex, Select the next shortest edge connected to either vertex, Repeat till all vertices have been connected with no cycles. Whilst doing so note the order and weight and at the end find the total weight.
- Prims Algorithm from a table: Start at A, delete row A, read down column A circle shortest edge, then delete the rest of that row, read down the columns of A and the other letter and repeat. Then formulate a graph noting down order and weight and calculate total weight at the end.
- Dijkstra's: Finds the shortest vertex to every other vertex in the network.
Imagens e arquivos do mapa
Informações
- Descrição
- AS - Level Further Maths Mapa Mental sobre Graphs & Networks, criado por 20257291 em 02-12-2015.
- Criado por
- 20257291
- Visualizações
- 1
- Avaliação













