Perfect 1-k Matchings of Bipartite Graphs

Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.

Results on energies for trees with a given diameter having perfect matching

Let Γd2nbe the set of trees with a given diameter d having a perfect matching,where 2n is the number of vertex.For a tree T in Γd2n,let Pd＋1be a diameter of T and q = d m,where m is the number of the edges of perfect matching inPd＋1.It can be found that the trees with minimal energy in Γd2nfor four cases q = d 2,d 3,d 4,[d2],and two remarks aregiven about the trees with minimal energy in Γd2nfor2d 33q d 5 and [d2] ＋ 1 q2d 33 1.

Induced Matching-Extendability of Halin Graphs

Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).

Numerical investigation of the effects of soil-structure and granular material-structure interaction on the seismic response of a flat-bottom reinforced concrete silo

In this work,a numerical study of the effects of soil-structure interaction(SSI)and granular material-structure interaction(GSI)on the nonlinear response and seismic capacity of flat-bottomed storage silos is conducted.A series of incremental dynamic analyses(IDA)are performed on a case of large reinforced concrete silo using 10 seismic recordings.The IDA results are given by two average IDA capacity curves,which are represented,as well as the seismic capacity of the studied structure,with and without a consideration of the SSI while accounting for the effect of GSI.These curves are used to quantify and evaluate the damage of the studied silo by utilizing two damage indices,one based on dissipated energy and the other on displacement and dissipated energy.The cumulative energy dissipation curves obtained by the average IDA capacity curves with and without SSI are presented as a function of the base shear,and these curves allow one to obtain the two critical points and the different limit states of the structure.It is observed that the SSI and GSI significantly influence the seismic response and capacity of the studied structure,particularly at higher levels of PGA.Moreover,the effect of the SSI reduces the damage index of the studied structure by 4%.

Unconditionally stable Crank-Nicolson algorithm with enhanced absorption for rotationally symmetric multi-scale problems in anisotropic magnetized plasma

Large calculation error can be formed by directly employing the conventional Yee’s grid to curve surfaces.In order to alleviate such condition,unconditionally stable CrankNicolson Douglas-Gunn(CNDG)algorithm with is proposed for rotationally symmetric multi-scale problems in anisotropic magnetized plasma.Within the CNDG algorithm,an alternative scheme for the simulation of anisotropic plasma is proposed in body-of-revolution domains.Convolutional perfectly matched layer(CPML)formulation is proposed to efficiently solve the open region problems.Numerical example is carried out for the illustration of effectiveness including the efficiency,resources,and absorption.Through the results,it can be concluded that the proposed scheme shows considerable performance during the simulation.

The Application of the Nonsplitting Perfectly Matched Layer in Numerical Modeling of Wave Propagation in Poroelastic Media

The nonsplitting perfectly matched layer （NPML） absorbing boundary condition （ABC） was first provided by Wang and Tang （2003） for the finite-difference simulation of elastic wave propagation in solids. In this paper, the method is developed to extend the NPML to simulating elastic wave propagation in poroelastic media. Biot＇s equations are discretized and approximated to a staggered-grid by applying a fourth-order accurate central difference in space and a second-order accurate central difference in time. A cylindrical twolayer seismic model and a borehole model are chosen to validate the effectiveness of the NPML. The results show that the numerical solutions agree well with the solutions of the discrete wavenumber （DW） method.

A study of perfectly matched layers for joint multicomponent reverse-time migration

Reverse-time migration in finite space requires effective boundary processing technology to eliminate the artificial truncation boundary effect in the migration result.On the basis of the elastic velocity-stress equations in vertical transversely isotropic media and the idea of the conventional split perfectly matched layer（PML）,the PML wave equations in reverse-time migration are derived in this paper and then the high order staggered grid discrete schemes are subsequently given.Aiming at the＂reflections＂from the boundary to the computational domain,as well as the effect of seismic event＇s abrupt changes at the two ends of the seismic array,the PML arrangement in reverse-time migration is given.The synthetic and real elastic,prestack,multi-component,reverse-time depth migration results demonstrate that this method has much better absorbing effects than other methods and the joint migration produces good imaging results.

Perfectly matched layer-absorbing boundary condition for finite-element time-domain modeling of elastic wave equations

The perfectly matched layer （PML） is a highly efficient absorbing boundary condition used for the numerical modeling of seismic wave equation. The article focuses on the application of this technique to finite-element time-domain numerical modeling of elastic wave equation. However, the finite-element time-domain scheme is based on the second- order wave equation in displacement formulation. Thus, the first-order PML in velocity-stress formulation cannot be directly applied to this scheme. In this article, we derive the finite- element matrix equations of second-order PML in displacement formulation, and accomplish the implementation of PML in finite-element time-domain modeling of elastic wave equation. The PML has an approximate zero reflection coefficients for bulk and surface waves in the finite-element modeling of P-SV and SH wave propagation in the 2D homogeneous elastic media. The numerical experiments using a two-layer model with irregular topography validate the efficiency of PML in the modeling of seismic wave propagation in geological models with complex structures and heterogeneous media.

关于3正则图的三匹配交猜想 (Ⅱ)(英文)

In 1994, FAN and RASPAUD posed the following conjecture: every bridgeless cubic graph contains three perfect matchings M 1, M 2 and M 3 such that M 1∩M 2∩M 3=*I.In this paper we obtain the following result: let G be a cyclely-4-edge-connected cubic graph, which has a perfect matching M 1 such that G-M 1 consists of four odd cycles. Then G contains two perfect matchings M 2 and M 3 such that M 1∩M 2∩M 3=*I.

A study of damping factors in perfectly matched layers for the numerical simulation of seismic waves

When simulating seismic wave propagation in free space, it is essential to introduce absorbing boundary conditions to eliminate reflections from artificially trtmcated boundaries. In this paper, a damping factor referred to as the Gaussian dmping factor is proposed. The Gaussian damping factor is based on the idea of perfectly matched layers （PMLs）. This work presents a detailed analysis of the theoretical foundations and advantages of the Gaussian damping factor. Additionally, numerical experiments for the simulation of seismic waves are presented based on two numerical models： a homogeneous model and a multi-layer model. The results show that the proposed factor works better. The Gaussian damping factor achieves a higher Signal-to-Noise Ratio （SNR） than previously used factors when using same number of PMLs, and requires less PMLs than other methods to achieve an identical SNR.

MWI in Cylindrical Coordinates and Its Application

Based on FDTD difference expressions and eigenfunctions of Maxwell functions in cylindrical coordinates, mesh wave impedances (MWIs) in 2D and 3D cylindrical coordinates were introduced. Combined with the concept of perfectly matched layer (PML), MWI PML absorbing boundary condition (ABC) algorithm was deduced in 2D cylindrical coordinates. Numerical experiments were done to investigate the validity of MWI and its application in cylindrical coordinates FDTD algorithm. The results showed that MWI in cylindrical coordinates can be used to accurately calculate the numerical reflection error caused by different mesh increments in non uniform FDTD. MWI can also provide theoretical criterion to define the permitted variable range of mesh dimension. MWI PML ABC is easy to be applied and reduces low numerical reflection, which only causes a little higher reflection error compared with Teixeira's PML.

INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS

It is said that a graph G is independent-set-deletable factor-critical （in short, ID-factor-critical）, if, for everyindependent-set I which has the same parity as ｜V（G）｜, G - I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The κ-th power of G, denoted by G^κ, is the graph with vertex set V（G） in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G^3 and T（G） （the total graph of G） are ID-factor-critical, and G^4 （when ｜V（G）｜ is even） is strongly IM-extendable; if G is 2-connected, then D^2 is ID-factor-critical.

Investigation of composite electromagnetic scattering from ship-like target on the randomly rough sea surface using FDTD method

Composite electromagnetic scattering from a two-dimensional （2D） ship-like target on a one-dimensional sea surface is investigated by using the finite-difference time-domain （FDTD） method. A uniaxial perfectly matched layer is adopted for truncation of FDTD lattices.The FDTD updated equations can be used for the total computation domain by choosing the uniaxial parameters properly. To validate the proposed numerical technique,a 2D infinitely long cylinder over the sea surface is taken into account first.The variation of angular distribution of the scattering changing with incident angle is calculated. The results show good agreement with the conventional moment method. Finally,the influence of the incident angle,the polarization,and the size of the ship-like target on the composite scattering coefficient is discussed in detail.

Borehole-GPR numerical simulation of full wave field based on convolutional perfect matched layer boundary

The absorbing boundary is the key in numerical simulation of borehole radar.Perfect match layer(PML) was chosen as the absorbing boundary in numerical simulation of GPR.But CPML(convolutional perfect match layer) approach that we have chosen has the advantage of being media independent.Beginning with the Maxwell equations in a two-dimensional structure,numerical formulas of finite-difference time-domain(FDTD) method with CPML boundary condition for transverse electric(TE) or transverse magnetic(TM) wave are presented in details.Also,there are three models for borehole-GPR simulation.By analyzing the simulation results,the features of targets in GPR are obtained,which can provide a better interpretation of real radar data.The results show that CPML is well suited for the simulation of borehole-GPR.

PML and CFS-PML boundary conditions for a mesh-free finite difference solution of the elastic wave equation

Mesh-free finite difference(FD)methods can improve the geometric flexibility of modeling without the need for lattice mapping or complex meshing process.Radial-basisfunction-generated FD is among the most commonly used mesh-free FD methods and can accurately simulate seismic wave propagation in the non-rectangular computational domain.In this paper,we propose a perfectly matched layer(PML)boundary condition for a meshfree FD solution of the elastic wave equation,which can be applied to the boundaries of the non-rectangular velocity model.The performance of the PML is,however,severely reduced for near-grazing incident waves and low-frequency waves.We thus also propose the complexfrequency-shifted PML(CFS-PML)boundary condition for a mesh-free FD solution of the elastic wave equation.For two PML boundary conditions,we derive unsplit time-domain expressions by constructing auxiliary differential equations,both of which require less memory and are easy for programming.Numerical experiments demonstrate that these two PML boundary conditions effectively eliminate artificial boundary reflections in mesh-free FD simulations.When compared with the PML boundary condition,the CFS-PML boundary condition results in better absorption for near-grazing incident waves and evanescent waves.

A PML Method for Electromagnetic Scattering from Two-dimensional Overfilled Cavities

In this paper, we consider electromagnetic scattering problems for two-dimensional overfilled cavities. A half ringy absorbing perfectly matched layer （PML） is introduced to enclose the cavity, and the PML formulations for both TM and TE polarizations are presented. Existence, uniqueness and convergence of the PML solutions are considered. Numerical experiments demonstrate that the PML method is efficient and accurate for solving cavity scattering problems.

An Adaptive Uniaxial Perfectly Matched Layer Method for Time-Harmonic Scattering Problems

The uniaxial perfectly matched layer (PML) method uses rectangular domain to define the PML problem and thus provides greater flexibility and efficiency in deal- ing with problems involving anisotropic scatterers.In this paper an adaptive uniaxial PML technique for solving the time harmonic Helmholtz scattering problem is devel- oped.The PML parameters such as the thickness of the layer and the fictitious medium property are determined through sharp a posteriori error estimates.The adaptive finite element method based on a posteriori error estimate is proposed to solve the PML equa- tion which produces automatically a coarse mesh size away from the fixed domain and thus makes the total computational costs insensitive to the thickness of the PML absorb- ing layer.Numerical experiments are included to illustrate the competitive behavior of the proposed adaptive method.In particular,it is demonstrated that the PML layer can be chosen as close to one wave-length from the scatterer and still yields good accuracy and efficiency in approximating the far fields.

A Uniaxial Optimal Perfectly Matched Layer Method for Time-harmonic Scattering Problems

We develop a uniaxial optimal perfectly matched layer （opt PML） method for solving the time-harmonic scattering problems by choosing a particular absorbing function with unbounded integral in a rectangular domain. With this choice, the solution of the optimal PML problem not only converges exponentially to the solution of the original scatting problem, but also is insensitive to the thickness of the PML layer for sufficiently small parameter ε0. Numerical experiments are included to illustrate the competitive behavior of the proposed optimal method.

ANALYSIS OF FDTD TO UPML FOR MAXWELL EQUATIONS IN POLAR COORDINATES

An FDTD system associated with uniaxial perfectly matched layer（UPML） for an electromagnetic scattering problem in two-dimensional space in polar coordinates is considered.Particularly the FDTD system of an initial-boundary value problems of the transverse magnetic（TM） mode to Maxwell＇s equations is obtained by Yee＇s algorithm,and the open domain of the scattering problem is truncated by a circle with a UPML.Besides,an artificial boundary condition is imposed on the outer boundary of the UPML.Afterwards,stability of the FDTD system on the truncated domain is established through energy estimates by the Gronwall inequality.Numerical experiments are designed to approve the theoretical analysis.

约束编程及其在单循环赛编排问题的应用研究

为解决单循环赛的赛程编排问题,提出了基于约束编程的统一编排求解模式。同时设计与实现了perfect-matching约束用于单循环赛编排问题的约束建模。对比分析在使用和不使用perfect-matching约束对问题建模时的求解性能,实验结果表明在对大规模的复杂的单循环赛进行编排时,perfect-matching约束能够极大提高求解的效率。