# A Diagnosability-Integrated Design Approach Based on Graph Theory
## 3 Diagnosability Integrated Design Method Details
### Measurement Point Determination
#### 3.1.3 Maximal Clique Set Selection Algorithm Based on Hypergraph  
Through the above analysis, it can be seen that the structure of the maximal clique found in the diagnosis plot of measurement point represents the system states that can be most easily distinguished using the information of the measurement point; so, maximal clique structure is the basis of designing fault diagnosis classifier. However, it was obvious that the maximal clique of measurement points did not necessarily contain all the states of the system, and so, a single maximal clique cannot correctly identify the state of the system. Therefore, multiple maximal cliques are needed to jointly identify the fault state of the system. Therefore, it is the main problem addressed in this section to select a suitable set of maximal cliques from among many maximal cliques to facilitate the detection and isolation of system faults.  
1. Problem Description  
The problem in this section can be described formally as follows:  
For the aforementioned system, suppose the set of maximal cliques of the system is \(\mathcal{C}=\left\{\mathcal{C}_{t_{i}}^{p}\right\}\), \(i=1,2,\cdots,n\). Now, it is necessary to choose the optimal set of maximal cliques \(\mathcal{C}^{\star}\) for the maximal cliques in \(\mathcal{C}\) such that \(\underset{\mathcal{C}_{t_{i}}^{p}\in\mathcal{C}^{\star}}{\cup}\mathcal{C}_{t_ {i}}^{p}=\mathcal{F}\), while ensuring that \(\min|\mathcal{C}^{\star}|\).  
Figure 4: Schematic diagram of sample distribution for different diagnosis plot of measurement point.  
Problem solving  
In this section, the above problem is solved based on the concept of hypergraph (Definitions 2 and 3).  
**Definition 2** (Hypergraph): _Given the undirected hypergraph \(\mathcal{H}=(\mathcal{V},\epsilon)\), the hypergraph vertex set is defined as \(\mathcal{V}=\{v_{1},v_{2},\cdots,v_{m}\}\), which contains \(m\) hypergraph vertices. The set of hypergraph edges is defined as a set \(\epsilon=\{\epsilon_{1},\epsilon_{2},\cdots,\epsilon_{n}\}\) containing \(n\) hypergraph edges, where for any hypergraph edge \(v\) in the set of hypergraph edges \(\epsilon\), \(\epsilon=\left\{\epsilon_{1}^{\prime},\epsilon_{2}^{\prime},\cdots,\epsilon_{ p}^{\prime}\right\}\), it means that the hypergraph edge has \(p\) hypergraph vertices._  
**Definition 3** (Edge Coverage): _Given the hypergraph \(\mathcal{H}=(\mathcal{V},\epsilon)\), \(C\subseteq\epsilon\). \(C\) is said to be an edge covering of \(\mathcal{H}\) if each vertex is associated with at least one edge in \(C\)._  
The problem in this section can be converted to solving the edge covering problem in hypergraph: where the state of the system is equivalent to the vertex in hypergraph, and the maximal clique is the edge in hypergraph. For the edge-covering problem of hypergraph, the most classical method is to use a greedy algorithm to solve this problem, and the steps of this method are shown as follows (Algorithm 2).  
```
Input:\(\mathcal{C}=\left\{\mathcal{C}_{t_{i}}^{p}\right\}\), \(i=1,2,\cdots,n\) \(\mathcal{F}=\left\{f_{0},f_{1},\cdots,f_{m}\right\}\) Output:\(C^{*}\)
01. initialize:\(X\leftarrow\mathcal{F}\), \(C^{*}\leftarrow\varnothing\) while\(X=\varnothing\)do
03. select \(\mathcal{C}_{t_{i}}^{p}\), so that it can cover most fault in \(X\)
04. \(C^{*}=C^{*}\cup\left\{\mathcal{C}_{t_{i}}^{p}\right\}\)
05. \(X=X\backslash F\)
06. endwhile
07. Return \(C^{*}\)
```  
**Algorithm 2** the set of maximal cliques \(C^{*}\) determination