What is a spanning tree?

Spanning tree is an important field in both mathematics and computer science. Mathematically, we define a spanning tree T of an un-directed and connected graph G as a tree consisting of all the vertices and all or some edges of the graph G.

- Spanning tree is defined as a selection of some edges from G forming a tree such that every vertex is spanned by it. 

- This means that every vertex of graph G is present in the spanning tree but there are no loops or cycles. 

- Also, every bridge of the given graph must be present in its spanning tree. 

- We can even say that a maximal set of the graph G’s edges containing no cycle or a minimal set of the graph G’s vertices forms a spanning tree. 

- In the field of graph theory, it is common finding the MST or the minimum spanning tree for some weighted graph. 

- There are a number of other optimization problems that require using the minimum spanning trees and other types of spanning trees. 

The other types of spanning trees include the following:

Ø  Maximum spanning tree

Ø  An MST spanning at least k number of vertices.

Ø  An MST having at the most k number of edges per vertex i.e., the degree constrained spanning tree.

Ø  Spanning tree having the largest no. of leaves (this type of spanning tree bears a close relation with the “smallest connected dominating set”).

Ø  Spanning tree with the fewest number of leaves (this spanning tree bears a close relation with the “Hamiltonian path problem”).

Ø  Minimum diameter spanning tree.

Ø  Minimum dilation spanning tree.

- One characteristic property of the spanning trees is that they do not have any cycles. 

- This also means that if you add just an edge to the tree, a cycle will be created. 

- We call this cycle as the fundamental cycle. 

- For each edge in the spanning there exists a distinct fundamental cycle and therefore there arises a one – to – one correspondence among the edges that are not present and the fundamental cycles. 

- For a graph G that is connected and has V vertices, there are V-1 edges in its spanning tree. 

- Therefore, for a general graph composed of E edges, its spanning tree will have E-V+1 number of fundamental cycles.

- For the cycle space of a given spanning tree these fundamental cycles are used. 

- The notion of the fundamental cut set as well as of the fundamental cycle forms a dual.  

- If we delete even one edge from the spanning tree, two disjoint sets will be formed of the vertices. 

- The set of the edges that if taken out from the graph G partitioning the vertices in to same disjoint sets is defined as the fundamental cut set. 

- For a given graph G there are V-1 fundamental cut sets i.e., one corresponding to each spanning tree edge. 

- The fact that the edges of the cycles that do not appear in the spanning tree but only in the cut sets of the edges can be used to establish the relationship between the cycles and the cut sets.

What is Spanning Forest?

- The sub-graph generalizing the spanning tree concept is called the spanning forest. 

- A spanning forest can be defined as a sub-graph consisting in each of the connected component a spanning tree of the graph G or we can call it a maximal cycle free sub graph.

- For counting the number of spanning trees for a complete graph the formula used is known as the cayley’s formula.

Explain the single and multiple partition techniques?

There are a number of allocation techniques available and all have different properties and allocate memory based on different principles. One prominent type of allocation is the partitioned allocation. 

- In partitioned allocation the primary or the main memory of the system is divided into a number of contiguous memory blocks which are commonly known as the memory partitions. 

- Each of these partitions consists of all the information that might be required for carrying out a specific task. 

- The task of allocating these memory partitions to various jobs and processes and de-allocating them after use is the duty of the memory management unit.  

- But partitioned allocation cannot be carried out by the help of software alone. 

- It requires some hardware support. 

- This support prevents interference of the various jobs in to each other and with the operating system as well. 

- For example, a lock and key technique was used by the IBM system/ 360. 

- Some other systems made use of the registers called the base and bound registers containing the partition limits and these were also used for flagging if any invalid access was made. 

- Limits register was used by the UNIVAC 1108 having separate base and bound data and instructions. 

- A technique called the memory interleaving was used by this system for placing so called I banks and d banks in different memory modules. 

Partitions are of two types namely:

Ø  Static partitions: These are defined at the boot time or IPL (initial program load) or sometimes by the computer operator. An example of system using static partitions is IBM system/360 operating system multi-programming with MFT (fixed number of tasks).

Ø  Dynamic partitions: These are created automatically for the specified job. An example is of the IBM system/ 360 operating system multi-programming with MVT (variable number of tasks).

- The hardware typed memory such as the base and bound registers (GE – 635, PDP – 10 etc.), Burroughs corporation B5500 etc. is used for relocating the memory partitions. 

- The partitions that can be relocated can be compacted to form larger contiguous memory chunks in the main memory. 

- Some systems allow for swapping out the partitions to the secondary storage and in turn to some additional memory.

The partitioned allocation offers two types of allocation techniques namely:

1. Single partition techniques
2. Multiple partition techniques

- Single partition techniques are the ones that are used for the single time sharing partition for swapping in and out the memory partitions. 

- These techniques are used by the IBM’s TSO (time sharing option). 

- The multiple partition techniques are used in the multiple time sharing partition. 

- In DOS systems when the disk is partitioned, each of the memory partitions act as if it is an individual disk drive. 

- Partitioning is useful for the systems where there are more than one operating system. 

- Partitioning techniques are meant for increasing the efficiency of the disk. 

- Hard and soft partitioning is used on the apple Macintosh computers. 

- The creation, relocation and deletion of the memory partitions can be harmful for the data. 

- That’s why it is good to have back up of the data stored on your system. 

- Several issues have to be considered if you want to install more than one operating system on your computer. 

- Day by day disks are becoming less expensive and bigger. 

- You can go for separate disks for storing data and installing Oss. 

Black-Box Testing Method - Equivalence Partitioning

Equivalence partitioning is a method for deriving test cases.
- It divides the input domain into classes of data from which test cases are derived.
- It strives to define a test case that uncovers classes of errors, thereby reducing the total number of test cases that must be developed.
- Equivalence classes for an input condition is used for test case design.
- An equivalence class represents a set of valid or invalid states for input conditions.
- Input classes are known relatively early in the software process.
- An input condition is either a specific numeric value, range of values, set of related values or a boolean condition.

DEFINING EQUIVALENCE CLASSES FOR TESTING

If an input condition specifies a:
- SPECIFIES RANGE : one valid and two invalid equivalence classes are defined.
- REQUIRES SPECIFIC VALUE : one valid and two invalid equivalence classes are defined.
- SPECIFIES MEMBER OF SET : one valid and one invalid equivalence class are defined.
- BOOLEAN : one valid and one invalid equivalence class are defined.