Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

Normal Size Small Size show me how

# D1 Definitions

Question | Answer |
---|---|

Median member of a list? | 0.5(N+1) if N is odd and 0.5(N+2) if N is even; that is, always round up. |

What is a graph? | A graph consists of points (vertices) which are connected by lines (edges) |

What is a subgraph of a graph G? | A graph each of whose vertices and edges belongs to G. |

What is a network? | A graph with a number (weight) associated with each edge. |

What is the degree of a vertex? | The number of edges incident to it. |

What is a path? | A finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex of the next, and no vertex appears more than once. |

What is a cycle? | A closed path such that the end vertex of the last edge is the start vertex of the first edge. |

When are two vertices connected? | If a path exists between them. |

When is a graph connected? | When all of its vertices are connected to one another. |

What is a digraph? | A graph where all the edges have a direction associated with them. |

What is a tree? | A connected graph that lacks cycles. |

What is a spanning tree of a graph G? | A subgraph of G which includes all the vertices of G and is a tree. |

What is a minimum spanning tree? | A spanning tree such that the total length of its arcs is as small as possible. |

What is a complete graph? | A graph in which each of the vertices is linked by one edge to every other vertex. |

What is the total float? | F(i,j) = lj - ei - duration(i,j) |

What is a bipartite graph? | A graph consisting of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, and not vertices within either set. |

What is denoted by Kr and Krs? | The complete graph with r vertices; the complete bipartite graph with r and s vertices in respective sets. |

What is a matching? | A pairing of some of the members of a set X with elements of another set Y. |

What is a complete matching? | A matching such that each member of the set X is paired with a member of Y. |

Created by:
krollo