Module 3

Question 1

} system of roads, streets, pipes, aqueducts, power lines, or nearly any structure which
permits either vehicular movement or flow of some commodity
} figure made up of points (vertices) connected by non-intersecting curves (arcs)
} Model-based definition of ____

Answer 1

Networks

Question 2

} simplified version of a slice of reality
} Pattern, plan, representation (especially in miniature), or description designed to show
the main object or workings of an object, system, or concept
} Building blocks of theories, foundations of a science

Answer 2

Model

Question 3

Importance of Models:

Answer 3

} Possible to deliberately eliminate real world complexities
} Enabling greater comprehension
} Enable abstraction
} Possible to manipulate data and test relationships among the components of the
problem
} Allow generalizations
} Constitute a common language of scientific discourse

Question 4

Types of Models:

Answer 4

Iconic Models
Analog Models
Symbolic Models

Question 5

} all the properties and relationships of the original phenomenon are represented at a
reduced scale
} Examples : Model trains; Aerial photographs

Answer 5

Iconic Models

Question 6

} only those characteristics of the real world considered to be significant are
incorporated.
} Certain level of abstraction
§ (from the Latin abs, meaning away from and trahere, meaning to draw)
§ certain things are eliminated, others are shown in stylized manner
§ analogy is drawn between phenomena in apparently disparate fields
} Example: Topographic Map; Globe

Answer 6

Analog Models

Question 7

} relationships are expressed usually by mathematical symbols in equation form
} Example: E=mc2

Answer 7

Symbolic Models

Question 8

} set of systematically organized points and lines
} a collection of vertices or nodes and a collection of edges that connect pairs of
vertices
} a set of vertex (nodes) v connected by edges (links) e. Thus G=(v , e).

Answer 8

Graphs

Question 9

Major properties of ordinary graphs:

Answer 9

} A network has a finite number of places
} Each route is a set consisting of two places
} Each route joins two different places
} At the most, only one route may join a pair of places
} No distinctions are made between the initial and the terminal places or
routes
} Routes are two-way

Question 10

The origins of graph theory can be traced to ____ who devised in 1735
a problem that came to be known as the “_____”.

Answer 10

Leonhard Euler, Seven Bridges of Konigsberg

Question 11

} branch of combinatorial topology
} Allows us to disentangle the basic structure of transportation

Answer 11

Graph Theory

Question 12

A ____ is a terminal point or an intersection point of a graph. It is the
abstraction of a location such as a city, an administrative division, a road intersection or a
transport terminal (stations, terminuses, harbors and airports).

Answer 12

Vertex (Node)

Question 13

An ___ is a link between two nodes. The link (i , j) is of initial
extremity i and of terminal extremity j. A link is the abstraction of a transport infrastructure
supporting movements between nodes. It has a direction that is commonly represented as
an arrow. When an arrow is not used, it is assumed the link is bi-directional.

Answer 13

Edge (Link)

Question 14

A ___ is a subset of a graph G where p is the number of ___. For instance G’ = (v’, e’) can be a distinct ___ of G. Unless the global transport system is considered in its whole, every transport network is in theory a ___ of
another. For instance, the road transportation network of a city is a ___ of a regional
transportation network, which is itself a ___ of a national transportation network.

Answer 14

Sub-Graph

Question 15

A link that makes a node correspond to itself is a ___.

Answer 15

Buckle (Loop or Self-Edge)

Question 16

A graph that includes only
one type of link between its nodes. A road
or rail network are ____?

Answer 16

Simple Graph

Question 17

A graph that includes several
types of links between its nodes. Some
nodes can be connected to one link type
while others can be connected to more than
one that are running in parallel. A graph
depicting a road and a rail network with
different links between nodes serviced by
either or both modes is a ____?.

Answer 17

Multigraph

Question 18

____ have nodes connected by only one link type, such as road or rail links. A ___ can contain more than one link type between the same two nodes (a combination of two ____ graphs).

Answer 18

Simple Graph, Multigraph, Simple

Question 19

A ____ enables flows of people, freight or information, which are
occurring along its links.

Answer 19

Transportation Network

Question 20

Graph theory must thus offer the possibility of representing
movements as linkages, which can be considered over several aspects:

Answer 20

Connection
Path
Chain
Length of a Link, Connection, or Path
Cycle
Circuit
Clique
Cluster
Ego Network
Nodal Region
Dual Graph

Question 21

A set of two nodes as
every node is linked to the other. Considers
if a movement between two nodes is
possible, whatever its direction. Knowing
connections makes it possible to find if it is
possible to reach a node from another node
within a graph.

Answer 21

Connection

Question 22

A sequence of links that are
traveled in the same direction. For a ____ to
exist between two nodes, it must be
possible to travel an uninterrupted
sequence of links. Finding all the possible
paths in a graph is a fundamental attribute
in measuring accessibility and traffic flows.

Answer 22

Path

Question 23

A sequence of links having a connection in common with the other. Direction
does not matter.

Answer 23

Chain

Question 24

Refers to the label associated with a
link, a connection or a path. This label can be distance, the amount of traffic, the capacity or
any relevant attribute of that link. The ? of a path is the number of links (or
connections) in this path.

Answer 24

Length of a Link, Connection, or Path

Question 25

Refers to a chain where the initial and terminal node is the same and that does not use the same link more than once is a ___.

Answer 25

Cycle

Question 26

A path where the initial and terminal node corresponds. It is a cycle where all the links are traveled in the same direction. ____ are very important in transportation because several distribution systems are using ____ to cover as much territory as possible in one direction (delivery route).

Answer 26

Circuits

Question 27

A maximal complete subgraph where all vertices are connected

Answer 27

Clique

Question 28

Also called ____, it refers to a group of nodes having denser relationships with each other than with the rest of the network. A wide range of methods are used to reveal ____ in a network, notably they are based on modularity measures (intra- versus inter-cluster variance).

Answer 28

Cluster, Community, Clusters

Question 29

For a given node, the ____ corresponds to a sub-graph where only its adjacent neighbors and their mutual links are included.

Answer 29

Ego Network

Question 30

Refers to a subgroup (tree) of nodes polarized by an independent node (which largest flow link connects a smaller node) and a number of subordinate nodes (which largest flow link connects a larger node). Single or multiple linkage analysis methods are used to reveal such regions by removing secondary links between nodes while keeping only the heaviest links.

Answer 30

Nodal Region

Question 31

A method in space syntax that considers edges as nodes and nodes as edges. In urban street networks, large avenues made of several segments become single nodes while intersections with other avenues or streets become links (edges). This method is particularly useful to reveal hierarchical structures in a planar network.

Answer 31

Dual Graph

Question 32

} Entails a certain amount of abstraction, simplification and generalization } Not scaled, spatial sequence is maintained } Focus is on the connections between places } Island boundary was eliminated } Forks in the road network where settlement nodes do not exist have been eliminated } Information loss acceptable } Graph eliminates the flesh and blood but retains the skeleton of the network } Links join specific places } Definite arrangement

Answer 32

Martinique Network

Question 33

By reducing the complex transportation network to its fundamental elements of nodes and links, it is possible to evaluate alternative structures; this can be done using ____.

Answer 33

Graph Theory

Question 34

This is the intersection of 2 edges which is always a vertex such as an Interstate Highway System. However, it is not always the case in ____ graph such as an Airline Network.

Answer 34

Planar, Non-Planar

Question 35

Distance between vertices is measured by counting the number of ___ separating them

Answer 35

Edges

Question 36

} degree of connection between all nodes in a system } Measure of the robustness of the network } Index of the relative simplicity or complexity of the network

Answer 36

Connectivity

Question 37

Two kinds of Connectivity:

Answer 37

§ Connectivity relating to individual vertices § Connectivity relating to the fineness and coarseness of the network as a whole

Question 38

k = max dij } maximum number of distances from vertex I to each of the other vertices } ____ – number of intervening edges between two vertices, measured along the shortest path, regardless of the actual mileage involved

Answer 38

Konig Index, Distance

Question 39

} Topological distance from a vertex to all others in the network } Based on the presence or absence of actual links } Most accessible place } can be reached with the shortest total topological distance than from any other nodes } does not follow that the geometric center of a region is the most accessible node

Answer 39

Accessibility Index

Question 40

} Measure the number of ways in which the ith node in a network can be reached from the jth node in a number of steps, assuming there is no direct connections between i and j subjourneys, connecting flights >> (Japan Airlines ) MLA – NRT – LAX (2 steps) >>(Hawaiian Airlines ) MLA – HNL – LAX (2 steps) >>(Continental Airlines) MLA – GUM – HNL – LAX (3 steps)

Answer 40

Multi-Step Connections

Question 41

Evaluating Vertex Connectivity:

Answer 41

} Connections are reciprocal } Some are better connected than others } Presence of intermediaries } Just as not all places are connected directly, so are individuals } Necessary to go through intermediaries } Connectivity matrix becomes useful to understand connections } Graph theoretic measures are useful in understanding not only accessibility but the connectivity of networks } Measures that have higher degree of utility in understanding transportation networks

Question 42

e/v } Number of linkages per place or nodes } Linkage intensity } Values of >1 suggests ___ routings } BI is high in developed countries, low in underdeveloped regions } Index value increases as alternative routings are constructed

Answer 42

Beta Index, Alternative

Question 43

e/(3(v-2)) } Ratio between the actual maximum possible number of edges in a graph } Planar graph; Non Planar Graph: [2e] / [v(v-1)] } Direct correlation with levels of economic development } Well connected networks are characterized with the presence of loops

Answer 43

Gamma Index

Question 44

} g – ____ } disjointed entities } evaluating network connectivity by counting loops } almost always __?

Answer 44

Cyclomatic Number, Subgraph, 1

Question 45

} –α= e –v + g or α= _μ_2v –5 2v –5 } Measuring ratio between the actual number of loops in a graph and the maximum possible number } Range: 0 – 1 for both planar and non-planar graphs

Answer 45

Alpha Index

Question 46

v n –D(G) = Σ Σ dij i= 1 j = 1 } Measures total distances between all vertices along the shortest paths } Evaluates the compactness of a network } Function of the spatial arrangement of vertices with reference to the network } i= 1 j = 1 } Measures total distances between all vertices along the shortest paths } Evaluates the compactness of a network } Function of the spatial arrangement of vertices with reference to the network } The value of the S.I. Is ___ related to the degree of compactness of a network

Answer 46

Dispersion or Shimbel Index (S.I.), Inversely

Question 47

Network Connectivity Summary } Number of linkages per place or nodes } Ratio between the actual and the maximum possible number of edges in a graph } Evaluating network connectivity by counting loops } Measures ratio between the actual number of loops in a graph and the maximum possible number } Measures total distances between all vertices along the shortest paths

Answer 47

} Beta Index } Gamma Index } Cyclomatic Number } Alpha Index } Dispersion/Shimbel Index

Question 48

Higher value, less connected (more peripheral (e.g. Optimal location for a train station)

Answer 48

Konig Index

Question 49

Low value, more connected (e.g. More places can be reached directly from particular node)

Answer 49

Accessibility Index

Question 50

Higher value, higher number of linkages per node (e.g. Developed countries have high values of ____. Alternative links may exist.)

Answer 50

Beta Index

Question 51

Higher value, higher accessibility between nodes (e.g. Richer countries have higher values due redundant links)

Answer 51

Gamma Index

Question 52

Higher value, higher connectivity of network (e.g. Richer countries have higher values due redundant links.)

Answer 52

Alpha Index

Question 53

Higher value, more connected network (e.g. Subgraphs may indicate early economic development stage

Answer 53

Cyclomatic Number

Question 54

Transport networks are functional (why and how?):

Answer 54

o Related to physical & socioeconomic context of a nation o Relatively advanced countries have higher index values than less developed ones o Technological innovation would help explain the reasons behind the index values

Question 55

Network Regionalization: } } }

Answer 55

} Certain pair of nodes are better connected than others } Nodes relatively close to one another may tend to be highly connected } Networks have hierarchical structure

Question 56

Nodes are linked in a variety of ways

Answer 56

Alternative Network Configuration

Question 57

Essential properties common to all hierarchies:

Answer 57

} Existence of two or more levels } Pyramidal structure } Number of objects at any one level decreases as we go up the hierarchy

Question 58

Nodal and Route Hierarchies Benefits: } } }

Answer 58

} Advantage of considering a network as a graph } Reduce it to its fundamental properties as nodes and links } All are of unit size and unit length

Question 59

*Smaller towns are ___ distances apart *As the size of the settlement increases, the average spacing between settlements of the same size also ____

Answer 59

Lesser, Increases

Question 60

*Two prime determinants of the volume of spatial interaction: * *

Answer 60

* Size of nodes * the distance between an origin & destination

Question 61

} Appropriate measure is the number of miles of different classes of routes } ____ evaluated according to their capacity to accommodate traffic } Large proportion of the total mileage consists of low-order, single track links of relatively short lengths } Relationships are not haphazard or random but occur in a patterned way which suggests functional order and spatial organization } ____ between transportation networks and drainage system

Answer 61

Route Hierarchies, Route Sizes, Isomorphism

Question 62

____ as independent variable contributing to variations in number, length, flow, and area.

Answer 62

Path Order

Question 63

Correspondence of Nodal and Route Hierarchies: } Large nodes, ___ order routes } ___that are fortuitously located are also connected by these routes } Smaller routes connect large nodes with ____ } In the real world, ____ are likely to be upgraded and low order nodes will also be served by ____

Answer 63

} High Order } Smaller Nodes } Smaller Nodes } Lower-order Routes, Higher order Links