click below

click below

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. |